信息学奥赛一本通 1394：连接格点(grid)

【题目链接】

ybt 1394：连接格点(grid)

【题目考点】

1. 图论：最小生成树

【解题思路】

该题和ybt 1393：联络员(liaison)考察内容是相同的。
每个点是一个图中顶点，相邻点可以连线。
题目中给的是坐标，我们需要把坐标数对和表示顶点编号的整数对建立映射关系，这样就可以通过坐标取到对应的顶点。
将题目中的x、y都减1，坐标就成了从0开始的数对。我们希望坐标和顶点编号有进行这样的对应关系
(0,0)–0， (0,1)–1， (0,2)–2， …， (0,n-1)–n-1
(1,0)–n， (1,1)–n+1， (1,2)–n+2， …， (1,n-1)–2n-1
(2,0)–2n， (2,1)–2n+1， (2,2)–2n+2， …， (2,n-1)–3n-1
…
(m-1, 0)–(m-1)n, (m-1, 1)–(m-1)n+1, …, (m-1, n-1)–mn-1
观察规律可知，坐标$(x,y)$对应的顶点编号为$xn+y$
每个点和其上下左右点都可以连线，相邻点之间当做有一条边，纵向的边权值为1，横向的边权值为2，建图。
在图中先选择已连线的边，也就是将已连接的边所连接的两个顶点所在集合合并。而后执行Kruskal算法，不断选择权值最小的边，如果该边两端的顶点不在同一集合（连通分量）中，就将两顶点所在集合合并。（如果当前权值最小的边是已连线的边，那么该边的两个顶点一定已经在同一集合中，不会进行再次合并。）选出的边和已有的边会构成一个权值加和最小的连通图，其原理见ybt 1393：联络员(liaison)。
行数、列数最大为$10^3$，顶点数量最大会达到$10^6$，每个顶点向右、向下连接一条边，连出的边数和图中的总边数接近，因此边数最大大约会达到$2\ast 10^6$个。Kruskal算法的复杂度为$O(ElogE)$，当E为$2\ast 10^6$时，算法运行总时间小于1s，可以通过。

【题解代码】

解法1：Kruskal算法

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
struct Edge
{int u, v, w;bool operator < (const Edge &b) const{return w < b.w;}
};
int m, n, fa[N], ans;
vector<Edge> edges;
void initFa(int n)
{for(int i = 0; i <= n; ++i)fa[i] = i;
}
int find(int x)
{return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y)
{fa[find(x)] = find(y);
}
void kruskal()
{sort(edges.begin(), edges.end());for(Edge e : edges){int u = e.u, v = e.v, w = e.w;if(find(u) != find(v)){merge(u, v);ans += w;}}
}
int nodeNum(int x, int y)//将坐标转为顶点编号 
{//x-1、y-1变为从0开始的行号和列号return (x-1)*n+(y-1);//在第x-1行(从0开始)，其上已经有(x-1)*n个元素，第y-1列，就是这一行已经过了y个元素，当前元素是从0开始的第(x-1)*n+y-1个元素 
}
int main()
{cin >> m >> n;initFa(m*n);//共m*n个顶点 int x1, y1, x2, y2;for(int x = 1; x <= m; ++x)for(int y = 1; y <= n; ++y){if(x+1 <= m)edges.push_back(Edge{nodeNum(x, y), nodeNum(x+1, y), 1});//一条竖线 	if(y+1 <= n)edges.push_back(Edge{nodeNum(x, y), nodeNum(x, y+1), 2});//一条横线			}while(cin >> x1 >> y1 >> x2 >> y2)merge(nodeNum(x1, y1), nodeNum(x2, y2));kruskal();cout << ans;return 0;
}