1394：连接格点(grid)
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
有一个M行N列的点阵，相邻两点可以相连。一条纵向的连线花费一个单位，一条横向的连线花费两个单位。某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通。
【输入】
第一行输入两个正整数m和n。
以下若干行每行四个正整数x1,y1,x2,y2，表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入保证|x1−x2|+|y1−y2|=1。
【输出】
输出使得连通所有点还需要的最小花费。
【输入样例】
2 2
1 1 2 1
【输出样例】
3
【提示】
【数据规模】
30%数据：n×m≤1000；
100%数据：m,n≤1000。
1. #include <iostream> 2. #include <cstdio> 3. #include <ctime> 4. 5. using namespace std; 6. 7. // 声明一个常量 N，并定义数组 p。N 的值为 1000005，即比 n*m 多了 5 8. const int N=1e6+5; 9. int n,m; 10. int p[N]; 11. 12. // 并查集的 Find 操作 13. int Fin(int x){ 14. // 如果父节点就是自己，返回它自己 15. if(p[x]==x) return x; 16. // 否则，递归地调用 Fin(p[x])，找到最终的祖先节点并记录下来 17. return p[x]=Fin(p[x]); 18. } 19. 20. // 并查集的 Union 操作 21. int Union(int x,int y){ 22. // 找到两个节点所在的集合的祖先节点 23. int xx=Fin(x); 24. int yy=Fin(y); 25. // 如果祖先不同，则将 yy 的祖先节点设置为 xx，表示将两个集合合并成一个 26. if(xx!=yy){ 27. p[yy]=xx; // 注意这里实际上只是修改 yy 祖先的父节点，而不是全部节点 28. return 1; 29. } 30. // 如果祖先相同，那么它们已经在一个集合中，不需要再次合并 31. return 0; 32. } 33. 34. int main() 35. { 36. cin>>n>>m; 37. // 初始化数组 p，将每个元素的父节点设置为自己 38. for(int i=1;i<=n*m;i++) p[i]=i; 39. 40. int x1,y1,x2,y2; 41. // 不断读入两个点的坐标，将它们加入同一个集合中 42. while(cin>>x1>>y1>>x2>>y2){ 43. // 二维坐标映射到一维坐标上 44. // 注意数组是从下标 1 开始存储的 45. Union((x1-1)*m+y1,(x2-1)*m+y2); 46. } 47. 48. int sum=0; 49. // 把每列相邻的元素放入同一个集合中，并记录操作次数 50. for(int i=1;i<=m;i++) 51. for(int j=1;j<n;j++){ 52. if(Union((j-1)*m+i,j*m+i)) sum++; 53. } 54. 55. // 把每行相邻的元素放入同一个集合中，并记录操作次数 56. for(int i=1;i<=n;i++) 57. for(int j=1;j<m;j++){ 58. if(Union((i-1)*m+j,(i-1)*m+j+1)) sum+=2; 59. } 60. 61. // 输出总共的操作次数，并结束程序 62. cout<<sum; 63. return 0; 64. }
