1 条题解

  • 0
    @ 2026-6-15 10:46:15

    // 最小生成树 Kruskal算法 O(N*M)
    #include<bits/stdc++.h>
    using namespace std;
    
    const int N=1010;
    int n,m,ans,fa[N*N];
    
    int find(int u){ //并查集的找根
      return fa[u]==u?u:fa[u]=find(fa[u]);
    }
    signed main(){
      cin>>n>>m;
      for(int i=1; i<=n*m; i++) fa[i]=i;
      for(int x1,y1,x2,y2;~scanf("%d%d%d%d",&x1,&y1,&x2,&y2);){
        int x=(x1-1)*m+y1,y=(x2-1)*m+y2;
        fa[find(x)]=find(y); //已知边加入并查集
      }
      
      // 先连竖边
      for(int i=1; i<n; i++)for(int j=1; j<=m; j++){
        int x=(i-1)*m+j, y=i*m+j;
        x=find(x), y=find(y);
        if(x!=y) fa[x]=y,ans++;
      }
      // 再连横边
      for(int i=1; i<=n; i++)for(int j=1; j<m; j++){
        int x=(i-1)*m+j, y=(i-1)*m+j+1;
        x=find(x), y=find(y);
        if(x!=y) fa[x]=y, ans+=2;
      }
      printf("%d\n",ans);
    }
    
    • 1

    D138 最小生成树 Kruskal 算法 U440253 连接格点

    信息

    ID
    12489
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    3
    已通过
    2
    上传者