这次要介绍一个很方便的简单易写的数据结构——并查集

由于我在集训的时候讲过并查集，鹅且这个也并不是科普入门博客，我就简单的上代码说原理了。

int f[maxn],r[maxn];
void init(){//首先创建f数组与r数组
    for(int i=0;i<n;i++)
        f[i]=i;//每一个节点一开始都是离散的，所以直接用i赋值
    //对于r数组，由于每一个节点一开始的深度都是0，所以直接memset
    memset(r,0,sizeof(r));
}

int find(int x){
    //这句可能会有点难理解，find函数是我们使用并查集的核心
    //最简单的原理就是我们一直通过f数组去找到并查集集合内树的顶点
    //然后在return的时候顺便保存到f数组内方便下次查找
    return f[x]=f[x]==x?x:find(f[x]);
}

void merge(int a,int b){
    //merge没什么难的，就是对f数组的操作
    //唯一需要的注意点就是当两个树的高度一致时需要选择一个子树的rank+1（画图理解）
    int x=find(a);
    int y=find(b);
    if(r[x]<r[y])
        f[x]=y;
    else{
        f[y]=x;
        if(r[x]==r[y])
            r[x]++;
    }
}

bool same(int x,int y){
    //这个函数简易到不写都行
    return find(x)==find(y);
}

接下来介绍的例题是hdu1863。

首先给出题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1863

畅通工程

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 42644 Accepted Submission(s): 19060

Problem Description

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。

Input

测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N
行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。

Output

对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。

Sample Input

Sample Output

1
2

3
?

Source

浙大计算机研究生复试上机考试-2007年

浙大复试上机是不是很刺激？！

这道题其实是有正面的做法和反推的做法的。

正面的做法比较简单，就是对所有的边按边权从小到大排序，然后使用并查集判断是否应该加边。

#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=200;

int f[maxn],r[maxn];
int n,m;

struct edge{
    int from,to,val;
}e[maxn];

bool cmp(edge a,edge b){
    return a.val<b.val;
}

void init(){
    for(int i=0;i<n;i++)
        f[i]=i;
    memset(r,0,sizeof(r));
}

int fin(int x){
    return f[x]=f[x]==x?x:fin(f[x]);
}

void merge(int x,int y){
    int a=fin(x),b=fin(y);
    if(r[a]<r[b])
        f[a]=b;
    else{
        f[b]=a;
        if(r[a]==r[b])
            r[a]++;
    }
}

bool same(int x,int y){
    return fin(x)==fin(y);
}

int main(){
    ios::sync_with_stdio(false);
    while(cin>>m>>n&&m){
        init();
        for(int i=0;i<m;i++) {
            cin >> e[i].from >> e[i].to >> e[i].val;
            e[i].from--;
            e[i].to--;
        }
        sort(e,e+m,cmp);
        int sum=0;
        for(int i=0;i<m;i++){
            if(same(e[i].from,e[i].to))
                continue;
            else{
                sum+=e[i].val;
                merge(e[i].from,e[i].to);
            }
        }
        int flag=1;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(!same(i,j)){
                    flag=0;
                    break;
                }
            }
        }
        if(flag)
            cout << sum << endl;
        else
            cout << '?' << endl;
    }
    return 0;
}

反面的做法我们可以这么假设，假设政府一条路都没造，我们为了联通n个城市至少需要建造n-1条路，那么只要我们使用并查集判断政府建造了多少条”有效的路径”，也就是说只要并查集查出这条路连通的不是同一个集合，就让ans-1，这样扫描所有建造的边就可以了。

In The End

数据结构:并查集

畅通工程