1 条题解
-
0

// 最小生成树 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
信息
- ID
- 12489
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 2
- 上传者