Daliy Algorithm (并查集)– day 97

Nothing to fear

种一棵树最好的时间是十年前，其次是现在！

那些你早出晚归付出的刻苦努力，你不想训练，当你觉的太累了但还是要咬牙坚持的时候，那就是在追逐梦想，不要在意终点有什么，要享受路途的过程，或许你不能成就梦想，但一定会有更伟大的事情随之而来。 mamba out~

2020.7.19

人一我十，人十我百，追逐青春的梦想，怀着自信的心，永不言弃！

关押罪犯

考点: 种类并查集

题目大意

一共由N个罪犯，每两个罪犯之间存在一个怨气值c，如果将这两人放在同一个监狱中则一定会造成影响力为c的暴力事件，局长为了保住自己的乌纱帽，需要将一年内发生的暴力事件的c值尽可能小。现在一共有两个监狱，问如何分配才能使得发生的暴力事件的c尽可能小。

分析

首先根据题意得每两人之间存在怒气值 c ,而这个c越大则发生得暴力事件越大。于是我们肯定是要将怒气值越大的两个人尽可能地分开。即安排再不同地监狱。那么我们如何对其进行操作呢？我们可以借鉴团伙中地思想，让其和敌人地敌人进行合并。待会再来证明这个贪心策略地正确性

1.首先对整个信息按照怒气值进行从大到小排序

2.当我们拿到两个人地信息，此时首先应该做的是尽可能拆散两人，即我们尽可能让A 和 B的敌人进行合并， B 和 A的敌人进行合并。

如果此时B记录的有敌人 那么 A 和 B的敌人进行合并，否则记录 A 为 B敌人。

B同理

if(!_next[e[i].a])_next[e[i].a] = e[i].b;
else Union(_next[e[i].a],e[i].b);
if(!_next[e[i].b])_next[e[i].b] = e[i].a;
else Union(_next[e[i].b],e[i].a);

此时如果检测到两个人已经在同一个集合中则退出

证明

如果此时输出的是 怒气值为 x 的事件， 说明此时必然有一对怒气值为 x 的人在同一个监狱，那么此时比 x 怒气值更大的人一定已经被分配到了不同的监狱，不然此时的答案就不会再是 x 。

反证：

假设 a 和 c有仇，b 和 c有仇。那么此时a 和 c在不同的监狱,b 和 c也在不同的监狱，那么a 和 b一定在同一个监狱。可此时如果a 和 b也有仇，但此时a 和 b又不在不同的监狱所以会产生矛盾可以直接输出 a b之间的仇恨值

完整代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

int n , m;
const int M = 100005;
const int N = 20005;
struct edge{
    int a, b, w;
}e[M];
int f[N] , _next[N];
bool cmp(edge a ,edge b)
{
    return a.w > b.w;
}
int find(int k)
{
    if(k == f[k])return k;
    else return f[k] = find(f[k]);
}
void Union(int a,int b)
{
    int A = find(a) , B = find(b);
    f[A] = B;
}
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++)f[i] = i;
    for(int i = 1;i <= m;i ++)
    {
        cin >> e[i].a >> e[i].b >> e[i].w;
    }
    sort(e + 1 , e + m + 1, cmp);
    for(int i = 1;i <= m + 1;i ++)
    {
        if(find(e[i].a) == find(e[i].b))
        {
            printf("%d\n",e[i].w);
            break;
        }else{
            if(!_next[e[i].a])_next[e[i].a] = e[i].b;
            else Union(_next[e[i].a],e[i].b);
            if(!_next[e[i].b])_next[e[i].b] = e[i].a;
            else Union(_next[e[i].b],e[i].a);
        }
    }
    return 0;
}

集合

考点: 筛素数 ， 并查集

题目大意

很直接就不描述了。

分析

首先通过题意，集合合并分可知需要用到并查集，质数可知会用到素数筛法。

在这里我们采用欧拉线性筛。如果村暴力枚举的区间a-b并且求两个树枝间是否存在质数的肯定会很慢，只能得到80分，于是判定肯定存在一种别的方案。由于题目中说的是找到两个数具有公共的质因数。

首先我们已经筛选出来了一定范围内的素数。我们只需要判断该以该质数为因子的树有哪些即可，但是存在两种情况

1.这个数已经在其他集合中出现过，此时我们需要将以这个数为质数的集合都，合并到出现的那个数的集合上去。

2.如果该集合合法的内容只有一个元素，则不构成题目条件，故跳过.

for(int j = 1;i * j <= b;j ++)
{
    if(i * j < a)continue;
    if(vis[i * j])flag = true , id = find(i * j);
    t.push_back(i * j);
}
if(t.size() <= 1)continue;
if(flag){
    for(int j = 0;j < t.size() ;j ++)
        Union(id , t[j]),vis[t[j]] = 1;
}else{
    for(int j = 0;j < t.size() ;j ++)
        Union(i , t[j]) ,vis[t[j]] = 1;
}

需要注意的点:

完整代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1000005;
int prime[N] , f[N];
int vis[N],visit[N];
int a , b , p;
int find(int k)
{
    if(k == f[k])return k;
    else return f[k] = find(f[k]);
}
void Union(int x,int y)
{
    int A = find(x) , B = find(y);
    f[B] = A;
}
void init()
{
    for(int i = 1;i < N ;i ++)f[i] = i;
}
void Prime()
{
    memset(visit,0 , sizeof visit);
    memset(prime, 0 ,sizeof prime);
    for (int i = 2;i <= N; i++) {
        if (!visit[i]) {
            prime[++prime[0]] = i;      //纪录素数， 这个prime[0] 相当于 cnt，用来计数
        }
        for (int j = 1; j <= prime[0] && i*prime[j] <= N; j++) {
            visit[i*prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}
int main()
{
    init();Prime();
    cin >> a >> b >> p;
    for(int i = p;i <= b;i ++)
    {
        if(visit[i])continue;
        bool flag = false;int id = 0;
        vector<int> t;
        for(int j = 1;i * j <= b;j ++)
        {
            if(i * j < a)continue;
            if(vis[i * j])flag = true , id = find(i * j);
            t.push_back(i * j);
        }
        if(t.size() <= 1)continue;
        if(flag){
            for(int j = 0;j < t.size() ;j ++)
                Union(id , t[j]),vis[t[j]] = 1;
        }else{
            for(int j = 0;j < t.size() ;j ++)
                Union(i , t[j]) ,vis[t[j]] = 1;
        }
    }
    memset(vis,  0 , sizeof vis);
    int cnt = 0;
    for(int i = a;i <= b;i ++)
    {
        //printf("f[%d] = %d\n",i , f[i]);
        if(vis[find(i)])continue;
        vis[find(i)] = 1;cnt++;
    }
    cout << cnt << endl;
}