（ssl 2348）连接格点#kruskal，并查集#

本文主要是介绍（ssl 2348）连接格点#kruskal，并查集#，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

有一个$M$行$N$列的点阵，相邻两点可以相连。一条纵向的连线花费一个单位，一条横向的连线花费两个单位。某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通。

分析

容我解释测试点

所以，既然求最小生成树，纵向优先。
那怎样连呢,Kruskal
首先一件重要的事情就是并查集是一维的。
所以$（x，y）$用$（x-1）\ast n+y$表示

---

代码

#include <cstdio>
using namespace std;
int f[10000001],n,m,x1,x2,y1,y2,s,p,q;
int father(int u){//求祖先if (f[u]==u) return u; return f[u]=father(f[u]);
}
int main(){scanf("%d%d",&m,&n);for (int i=1;i<=m*n;i++) f[i]=i;while (scanf("%d%d%d%d",&x1,&x2,&y1,&y2)==4){p=father((x1-1)*n+x2); q=father((y1-1)*n+y2);if (p!=q) f[q]=p;//合并}for (int i=1;i<=n;i++)for (int j=1;j<m;j++){p=father((j-1)*n+i);q=father(j*n+i);if (p!=q) {f[q]=p;s++;}}//纵优先for (int i=1;i<=m;i++)for (int j=1;j<n;j++){p=father((i-1)*n+j);q=father((i-1)*n+j+1);if (p!=q){f[q]=p;s+=2;}}printf("%d",s); return 0;
}

这篇关于（ssl 2348）连接格点#kruskal，并查集#的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---