CQUPT 集训队专题训练（并查集/生成树）

并查集 最小生成树

题目链接

A - How Many Tables

题意

互相认识的人可以同坐一张桌子，间接认识也可以，但是丝毫不认识的不能共坐一张桌子，每张桌子能做无数人，请问最少多少张桌子能容纳下所有人

思路

并查集查找独立集合的个数即可

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
const int N = 1007;
typedef long long LL;
int p[N];

void init(int n){
    for(int i = 1 ; i <= n ; i++)   p[i] = i;
}

int find(int x){
    if( p[x] != x ) return find(p[x]);
    return p[x];
}

void bcj(int a, int b,int n){
    a = find(a);
    b = find(b);
    if( a != b )    p[a] = b;
}

int cx(int n){
    int cnt = 0;
    //for( int i = 1 ; i <= n ; i++ )   printf("%4d",p[i]);printf("\n");
    for( int i = 1 ; i <= n ; i++ ) if( p[i] == i ) cnt++;
    return cnt;
}

int main(){
    int T,n,m;
    scanf("%d",&T);
    while( T-- ){
        scanf("%d%d",&n,&m);
        init(n);
        int a,b;
        for(int i = 0 ; i < m ; i++){
            scanf("%d%d",&a,&b);
            bcj(a,b,n);
        }
        printf("%d\n",cx(n));
        //getchar();
    }
    return 0;
} 

B - Corporative Network

题意

 原本每个子公司都有自己的运算中心，但公司决定把一些子公司的运算中心合并；
1.输入I ——I   J  代表把集合I的运算中心连接到集合J的一家公司，J不一定为集合J的运算中心，I到J 的距离为（I-J）%1000。
2.输入E-----I   问公司I到其运算中心的距离。

思路

进行并查集的时候维护处理节点到达其运算中心的距离即可

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <cmath>
using namespace std;
const int N = 2e5+7;
const int MOD = 1000;
typedef long long LL;
int p[N] , d[N];

void init(int n){
    for(int i = 0 ; i <= n ; i++)   p[i] = i , d[i] = 0;
}

int abss(int x){
    return x >= 0 ? x : x * (-1);
}

int find(int x){
    if( x == p[x] ) return x;
    int root = find(p[x]);
    d[x] += d[p[x]];
    p[x] = root;
    return p[x];
}

int find1(int x){
    if( x != p[x] ) return find(p[x]);
    return x;
}

void bcj(int a , int b){
    p[a] = b;
    d[a] = abss(a - b) % MOD;
}

int main(){
    int T;
    char s;
    int a,b,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        init(n);

        while( true ){
            getchar();
            scanf("%c",&s);
            if( s == 'E' )  scanf("%d",&a),find(a),printf("%d\n",d[a]);
            else if(s == 'I')   scanf("%d%d",&a,&b) , bcj(a,b);
            else    break;
        }

    }
    return 0;
}

C - 卿学姐与诡异村庄

题意

告诉你村庄中每个人指控谁是否为好人，请问是否有个合理的分类能够符合所有的指控。

思路

用一个两倍长的数组存下两个状态的并查集
其中1--i---n表示第i位是好人，n+1---n+i---+n表示第i位是坏人
如果并查集的时候第i人好人坏人属于同一集合，那么就是不存在合理的分类，否则属于合理的分类

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <cmath>
using namespace std;
const int N = 2e5+7;
const int MOD = 1000;
typedef long long LL;
int p[N];
int a,n,t;

int init(){
       int len = n*2+1;
    for(int i = 0 ; i < len ; i++)  p[i] = i;
}

int find(int x){
    //printf("find(x = %d) , p[x] = %d\n",x,p[x]);
    if( p[x] == x ) return x;
    p[x] = find(p[x]);
    return p[x];
}

void p_push(int i,int ai,int t){
    int x[2],y[2];
    x[0] = ai;
    x[1] = ai+n;
    y[0] = i;
    y[1] = i+n;
    if( t == 1 ){
        for(int k = 0 ; k < 2 ; k++)    if( (x[k] = find(x[k])) != (y[k] = find(y[k])) )    p[y[k]] = x[k];
    }else   for(int k = 0 ; k < 2 ; k++)    if( (x[1-k] = find(x[1-k])) != (y[k] = find(y[k])) )    p[y[k]] = x[1-k];
}

int main(){
    bool can;
    while( scanf("%d",&n) != EOF ){
        init();
        for(int i = 1 ; i <= n ; i++){
            scanf("%d%d",&a,&t);
            p_push(i,a,t);
        }
        can = true;
        for(int i = 1 ; i <= n && can; i++) if( find(i) == find(i+n) )  printf("One face meng bi\n") , can = false;// else printf("now is test %d\n",i);
        if(can) printf("Time to show my power\n");
    }
    return 0;
} 

D - 食物链

题意

有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是"1 X Y"，表示X和Y是同类。
第二种说法是"2 X Y"，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

思路

借助js大神题解，类似C题，建立三种状态的并查集，一种是x吃y，x和y是同类，y吃x，然后每种动物对三种状态查询，其中对应匹配就是同类，右移一位为前者吃后者，反之则为后者吃前者，如果状态矛盾是假话，否则进行并查集操作
状态矛盾的情况有
1. 如果x和y是同类，且曾今说过x吃y或者y吃x
2. 如果查到y吃x，本句话无论是什么都是假话
3. 如果说x吃y，且曾今说过x和y是同类就是假话
在特判其他特殊不合法输入即可

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <cmath>
using namespace std;
const int N = 5e4+7;
const int MOD = 1000;
typedef long long LL;
int p[N*3];

int find(int x){
    if( x == p[x] ) return x;
    return p[x] = find(p[x]);
} 

int main(){
    int n,k,t,x,y,ans;
    scanf("%d%d",&n,&k);
    ans = 0;
    n*=3;
    for(int i = 1 ; i <= n ; i++)   p[i] = i;
    n/=3;
    for(int i = 0 , j; i < k ; i++){
        scanf("%d%d%d",&t,&x,&y);
        if( x > n || y > n ){
            ans++;
            continue;
        }else{
            int a[3] , b[3];
            for(j = 0 ; j < 3 ; j++)    a[j] = find(x+n*j) , b[j] = find(y+n*j);
            if( a[0] == b[2] ){
                ans++;
                continue;
            }
            else if( t == 1 )
                if( a[0] == b[1] )  ans++;
                else    for( j = 0 ; j < 3 ; j++)   p[a[j]] = p[b[j]];
            else
                if( a[0] == b[0] )  ans++;
                else    for( j = 0 ; j < 3 ; j++ )  p[a[j]] = p[b[(j+1)%3]];
        } 
    }
    printf("%d\n",ans);
    return 0;
}

E - Dark roads

题意

给定n个点,m条边，求解把所有点联通需要的最小边权值

思路

最小生成树模板题

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <cmath>
#include <queue>
using namespace std;
const int N = 2e5+7;
const int MOD = 1000;
typedef long long LL;

struct node{
    int form,to,dist;

    bool operator < (const node &a) const{
        return dist > a.dist;
    }

    node(int u , int v , int d):form(u),to(v),dist(d) {}
};

priority_queue<node> q;
int p[N] , n, m ,ans,all;

void init(){
    for(int i = 0 ; i < m ; i++ )   p[i] = i;
    while( !q.empty() ) q.pop();
    all = 0;
}

void bcj(int a, int b){
    if( p[a] == p[b] )  return;
    int c = p[b];
    for( int i = 0 ; i < m ; i++ )  if( p[i] == c ) p[i] = p[a];
}

bool ok(){
    int c = p[0];
    for(int i = 1 ; i < m ; i++)    if( p[i] != c ) return false;
    return true;
}

void solve(){
    ans = 0;
    while( !q.empty() ){
        node Q = q.top();q.pop();
        if( p[Q.form] == p[Q.to] )  continue;
        bcj(Q.form,Q.to);
        ans += Q.dist;
        if( ok() )  return;
    }
}

int main(){
    int u,v,d;
    while( scanf("%d%d",&m,&n) != EOF && n && m ){
        init();
        for(int i = 0 ; i < n ; i++)    scanf("%d%d%d",&u,&v,&d) , q.push(node(u,v,d)) , all+=d;
        solve();
        printf("%d\n",all - ans);
    }
    return 0;
}

F - Design Tutorial: Inverse the Problem

题意

问一个n*n邻接矩阵，问是否有一个n个点n-1条边的树能满足这个邻接矩阵

思路

先排除vis[i,i] != 0 或者vis[i,j] != vis[j,i]的情况
然后标记所有vis[1,i]*2的值，之后便利所有的边如果对于边vis[i,k]没发现其相等于vis[1,i]与vis[1,k]差得绝对值或者找到了vis[1,i]与vis[1,k]的和减去vis[i,k]这个值没被标记那么这个邻接矩阵就不能满足条件

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
using namespace std;
const int N = 2003;
const int MOD = 1000;
typedef long long LL;
const LL INF = 0x3fffffffffffffff;
int dis[N][N];
map<LL,int> m;

int main(){
    int n;
    bool can = true;
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; i++)
        for(int k = 1 ; k <= n ; k++)
            scanf("%lld",dis[i]+k);
    for(int i = 1 ; i <= n ; i++)
        for(int k = 1 ; k <= n ; k++)
            if( (i == k && dis[i][k] != 0) || (i != k && dis[i][k] == 0 ) || dis[i][k] != dis[k][i] ){
                printf("NO\n");
                return 0;
            }
    for(int i = 1 ; i <= n ; i++)
        m[2*dis[1][i]] = 1;
    for(int i = 1; i <= n ; i++)
        for(int k = 1 ; k <= n ; k++){
            if( dis[i][k] == abs(dis[1][i] - dis[1][k] ) || m[ dis[1][i]+dis[1][k]-dis[i][k] ] )    continue;
            printf("NO\n");
            return 0;
        }
    printf("YES\n");
    return 0;
}