链接 :
http://acm.pku.edu.cn/JudgeOnline/problem?id=3625题意 : 将所有农场链接的最小长度,即最小生成树。但是有的 边已经连接完毕
输入 :
4 1 // 4个点 1个已经连完的边
1 1 //点坐标
3 1
2 3
4 3
1 4 //连接完毕的点地编号
想法 :将连接完毕的点地权值更改为0,克鲁斯 + 并查 或者 将已经连接的点先并入一个集合
核心代码如下 :
1. 将已经连接的点先并入一个集合
1 for(i = 0; i < m; i++){
2 scanf("%d%d", &u, &v);
3 if((u = find(u)) != (v = find(v))){
4 f[u] = v;
5 n--;
6 }
7 }
2. 并查集合
int find(int x){
if(x != f[x])return f[x] = find(f[x]);
return f[x];
}
3. 克鲁斯卡尔 + 并查
1 tel = el;
2 make_heap(e, e + el, cmp);
3 for(i = 0; i < n - 1; tel--){
4 if((u = find(e[0].u)) != (v = find(e[0].v))){
5 f[u] = v;
6 sum += e[0].w;
7 i++;
8 }
9 pop_heap(e, e + tel, cmp);
10 }