莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 两维坐标变一维，方便后续操作
2. 先将已经存在的边连通起来
3. 先计算竖着的，再计算横着的

可参考： 联络员

#include<bits/stdc++.h>

using namespace std;

const int N = 1010, M = N * N, K = 2 * M;

int n,m,cnt;
int ids[N][N];
struct Edge
{
    int a,b,w;
}e[K];
int p[M];

//并查集基本操作
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

void get_edges()
{
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1},dw[4]={1,2,1,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%2==z)
                    {
                        int x=i+dx[u],y=j+dy[u],w=dw[u];
                        if(x&&x<=n&&y&&y<=m)
                        {
                            int a=ids[i][j],b=ids[x][y];
                            if(a<b) e[cnt++]={a,b,w};
                        }
                    }
}

int main()
{
    cin>>n>>m;

    //二维变一维
    for(int i=1,t=1;i<=n;i++)
        for(int j=1;j<=m;j++,t++)
            ids[i][j]=t;

    for(int i=1;i<=n*m;i++) p[i]=i;

    //已经连通了的边
    int x1,y1,x2,y2;
    while(cin>>x1>>y1>>x2>>y2)
    {
        int a=ids[x1][y1],b=ids[x2][y2];
        p[find(a)]=find(b);
    }

    get_edges();

    // Kruskal 基本操作
    int res=0;
    for(int i=0;i<cnt;i++)
    {
        int a=find(e[i].a),b=find(e[i].b),w=e[i].w;
        if(a!=b)
        {
            p[a]=b;
            res+=w;
        }
    }

    cout<<res<<endl;

    return 0;
}