连接格点

最小生成树 T3 信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

描述

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

输入

第一行输入两个正整数$m$和$n$, 其中 $1<=n,m<=1000$。

以下若干行每行四个正整数$x_1,y_1,x_2,y_2$，表示第$x_1$行第$y_1$列的点和第$x_2$行第$y_2$列的点已经有连线。输入保证$|x_1-x_2|+|y_1-y_2|=1$。

输出

输出使得连通所有点还需要的最小花费。

输入样例 1

2 2
1 1 2 1

输出样例 1

3

思路

一个无向图, 已经有一些边被确认, 求剩下边中选择一些, 使得整个图连通且总权值和最小。

跟联络员一题很像, 不过这里是矩阵点, 最大有$1000000$个点, 且边的权值已经固定, 竖着的权值为1, 横着的权值为2。由此可以省去Kruscal的排序操作, 我们枚举边时先枚举竖着的边, 再枚举横边即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1010, M = N * N, K = 2 * N * N;
int f[M];
int n, m, k;
int ids[N][N];
struct Edge
{
    int a, b, w;
} e[K];
 
int find(int x)
{
    return f[x] == x ? f[x] : f[x] = find(f[x]);
}
 
void get_edges()
{
    int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1}, dw[] = {1, 1, 2, 2};
 
    for (int z = 0; z < 2; z++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                for (int u = 0; u < 4; u++)
                {
                    if (u > 1 && !z || u <= 1 && z)
                        continue;
                    int x = i + dx[u], y = j + dy[u];
                    if (x < 1 || x > n || y < 1 || y > m)
                        continue;
 
                    int a = ids[i][j], b = ids[x][y], w = dw[u];
                    if (a > b)
                        continue;
                    e[k++] = {a, b, w};
                    //cout << a << " " << b << " " << w << endl;
                }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
 
    for (int i = 1, cnt = 1; i <= n; i++)
        for (int j = 1; j <= m; j++, cnt++)
            ids[i][j] = cnt;
 
    int x1, x2, y1, y2;
    long long res = 0;
    for (int i = 1; i <= n * m; i++)
        f[i] = i;
    while (cin >> x1 >> y1 >> x2 >> y2)
    {
        int a = find(ids[x1][y1]), b = find(ids[x2][y2]);
        f[b] = a;
    }
 
    get_edges();
 
    for (int i = 0; i < k; i++)
    {
        int a = find(e[i].a), b = find(e[i].b), c = e[i].w;
        if (a != b)
        {
            f[b] = a;
            res += c;
        }
    }
    cout << res << endl;
 
    return 0;
}