题目描述
有一个 \(m\) 行 \(n\) 列的点阵，相邻两点可以相连。
一条纵向的连线花费一个单位，一条横向的连线花费两个单位。
某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通。
解题思路
\(\qquad\)在输入的时候把已经有连线的点合并到同一个集合(通过并查集)，为了方便并查集的处理，我们将一个坐标点\((x,y)\)做一个映射：变成一维坐标\(x\times m +y\)这样就可以用一维的并查集了。
\(\qquad\)对于一开始不连通的点，我们观察边权可以得到一个贪心思路：纵连线一定是比横连线实惠的。所以我们就先连纵的。
\(\qquad\)当我们按照上面的策略连完纵向连线后，相当于得到一个这样的图：
\(\LARGE .代表格子，|代表纵向边\)
........（n列）
||||||||
........
||||||||
........
(m行)
所以这张图只要我们把第一行都连起来，就好了。
因此我们采取的策略就是：
\(\qquad\)首先按列枚举\(i ->\ (1\sim n)\),
\(\qquad\)对于每一列我们再按行枚举\(j->\ (1\sim n-1)\)，然后我们把这列上每一行的格子和它的下一行连线，并将统计的结果\(+1\)（花费），也就是连接坐标点\((j,i)和(j+1,i)\)
\(\qquad\)按列枚举后就是讲第一行的所有点连接了
\(\qquad\)这里只需要枚举\(i->(1\sim m-1)\)，连接所有的坐标\((1,i),1(i+1)\)就行
代码
#include <iostream>
#pragma GCC optimize(2)
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, M = N * N;
int p[M], n, m;
int get(int x, int y) { return x * m + y; }
struct Edge
{
int u, v, w;
bool operator <(const Edge& W) const {
return w < W.w ;
}
} edge[M];
int find(int x)
{
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d", &m, &n);
for (int i = 1; i <= m * m + n; i ++ ) p[i] = i;
int x1, y1, x2, y2;
while (~scanf("%d%d%d%d", &x1, &y1, &x2, &y2))
p[find(get(x1, y1))] = find(get(x2, y2));
int res = 0;
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j < m; j ++ )
{
int a = find(get(j, i)), b = find(get(j + 1, i));
if (a != b) p[a] = b, res ++ ;
}
}
for (int i = 1; i < n; i ++ )
{
int a = find(get(1, i)), b = find(get(1, i + 1));
if (a != b) p[a] = b, res += 2;
}
printf("%d\n", res);
return 0;
}