luogu P1546 最短网络 Agri-Net

#include<cstdio>#include<algorithm>using namespace std;#define maxn 20010int fa[maxn],n;int cnt,ans;struct EDGE { ???int to,from,weight;} edge[maxn];void add(int x,int y,int w) { ???edge[++cnt].to = y; ???edge[cnt].from = x; ???edge[cnt].weight = w;}int get(int x) { ???if(fa[x] == x) ???????return x; ???return fa[x] = get(fa[x]);}int cmp(EDGE x,EDGE y) { ???return x.weight < y.weight;}int kruskal() { ???for(int i = 1; i <= n; i++) ???????fa[i] = i; ???sort(edge + 1,edge + cnt + 1,cmp); ???for(int i = 1; i <= cnt; i++) { ???????int l = get(edge[i].from); ???????int r = get(edge[i].to); ???????if(l != r) { ???????????fa[l] = r; ???????????ans += edge[i].weight; ???????} ???} ???return ans;}int main() { ???scanf("%d",&n); ???for(int i = 1; i <= n; i++) ???????for(int j = 1; j <= n; j++) { ???????????int w; ???????????scanf("%d",&w); ???????????if(j > i) ???????????add(i,j,w); ???????} ???printf("%d",kruskal()); ???return 0;}