【BUAA 595】太空漫步
最小生成树
kruskal模板题
代码如下
;typedef struct Edge{int u,v,d;Edge a)const{return d < a.d;}}Edge;Edge eg[111111];int pre[111];int n,tp;void Init(){int i;for(i = 1; i <= n; ++i)pre[i] = i;}int Find(int x){if(x != pre[x]) pre[x] = Find(pre[x]);return pre[x];}void Add(int u,int v,int d){eg[tp].u = u;eg[tp].v = v;eg[tp++].d = d;}int main(){scanf(“%d”,&n);tp = 0;int i,j,d,cnt,sum,k,r;Init();for(i = 1; i <= n; ++i){for(j = 1; j <= n; ++j){scanf(“%d”,&d);if(i < j){Add(i,j,d);}}}sort(eg,eg+tp);cnt = sum = 0;for(i = 0; i < tp; ++i){k = Find(eg[i].u);r = Find(eg[i].v);if(k != r){pre[k] = r;sum += eg[i].d;cnt++;}if(cnt == n-1) break;}printf(“%d\n”,sum);return 0;}
，那段雨骤风狂。人生之旅本就是风雨兼程，是要说曾经拥有，
