思路与算法

先将所有已有连线的端点用并查集合并，已有连线费用不再支付。其余可能连线只有两种费用：纵向1、横向2。先枚举全部纵向邻居，对不同集合合并并累加1；再枚举横向邻居，对不同集合合并并累加2。无需保存边数组或调用排序。

正确性说明

把已有连通块视为收缩后的节点。所有待选边费用非负，Kruskal按费用递增、只在连接不同连通块时选边，可由割性质保证存在包含当前所选边的最小生成树。先纵后横就是完整权值顺序，跳过同集合边避免环。完整矩形网格本来连通，枚举完全部邻接边后必然全部连通，总费用最小。

复杂度

设V=mn。读已有边K，初始化并查集O(V)，隐式网格边数O(V)，按大小合并与路径压缩总时间O((V+K)α(V))，空间O(V)。m,n≤1000，父亲与大小两个int数组约8MB，不构造百万边对象。重复的已有边只产生无效合并。

易错点

纵向费用1、横向费用2，不能颠倒。坐标从1开始，压平为(x-1)*n+y-1。已有边只合并不收费；单格答案0，一行或一列仍须正常连通。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct DSU {
    vector<int> p, s;
    DSU(int n) : p(n), s(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int a) {
        while (p[a] != a) {
            p[a] = p[p[a]];
            a = p[a];
        }
        return a;
    }
    bool join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;
        if (s[a] < s[b])
            swap(a, b);
        p[b] = a;
        s[a] += s[b];
        return true;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n;
    cin >> m >> n;
    DSU d(m * n);
    int x, y, z, w;
    while (cin >> x >> y >> z >> w)
        d.join((x - 1) * n + y - 1, (z - 1) * n + w - 1);
    long long ans = 0;
    for (int i = 0; i + 1 < m; ++i)
        for (int j = 0; j < n; ++j)
            ans += d.join(i * n + j, (i + 1) * n + j);
    for (int i = 0; i < m; ++i)
        for (int j = 0; j + 1 < n; ++j)
            ans += 2 * d.join(i * n + j, i * n + j + 1);
    cout << ans << '\n';
}