构建出所有的边然后跑kruskal算法选出最小生成树。有几点需要注意

• 边权只有1、2，因此可以先建立竖边在建立横边。这样就可以不用排序
• 先建立竖边在建立横边需要借助z和取余完成
• 为了配合并查集使用 将二维坐标转化成一维坐标的方式

#include<iostream>
using namespace std;
const int N=1010,M=N*N;
int ids[N][N],p[M];
int n,m,k;
//横边纵边分别N*N
struct Edge{
    int a,b,w;
}e[2*M];

int find(int x){
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];

}

void get_edge(){
    int dx[]={-1,0,1,0},dy[]={0,1,0,-1},dz[]={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=dz[u];
                        if(x&&x<=n&&y&&y<=m){
                            int a=ids[i][j],b=ids[x][y];
                            if(a<b) e[k++]={a,b,w};
                        }
                    }
                }
}

int main(){
    cin>>n>>m;
    //**
    for(int i=1;i<=n*m;i++) p[i]=i;

    for(int i=1,t=1;i<=n;i++)
        for(int j=1;j<=m;j++,t++)
            ids[i][j]=t;

    int x1,x2,y1,y2;
    while(cin>>x1>>y1>>x2>>y2){
        int a=find(ids[x1][y1]),b=find(ids[x2][y2]);
        p[a]=b;
    }

    get_edge();

    int res=0;

    for(int i=0;i<k;i++){
        int a=find(e[i].a),b=find(e[i].b),w=e[i].w;
        if(a!=b){
            res+=w;
            p[a]=b;
        }
    }

    cout<<res;
    return 0;
}