P1546 [USACO3.1] 最短网络 Agri-Net

[题目通道]([USACO3.1] 最短网络 Agri-Net - 洛谷)

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e6+100;
struct edge{int u,v,w;
}e[N*30];
bool cmp(edge a,edge b){return a.w<b.w;
}
int a,b,c,n,m,fa[N],cnt=0,ans=0;
int find(int x){if (fa[x]==x) return x;else return fa[x]=find(fa[x]);
}
signed main(){cin>>n;for (int i=1;i<=n;i++){fa[i]=i;}int x,y;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&x);if(j>i) {m++;e[m].u=i;e[m].v=j;e[m].w=x;}}}sort(e+1,e+m+1,cmp);for (int i=1;i<=m;i++){int fu=find(e[i].u);int fv=find(e[i].v);if (fu!=fv){cnt++; ans+=e[i].w; fa[fu]=fv;if (cnt==n-1) {cout<<ans;return 0;}}} return 0;
}