emmm

题面不想放了

传送门www

一道emmm

很简单的最小生成树问题

没啥思维含量

不知道因为什么zz问题写了4遍www

#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;}

总之，做最小生成树的时候还是要注意细节啊