【BUAA 595】太空漫步

【BUAA 595】太空漫步

最小生成树

kruskal模板题

代码如下

#include using namespace std;typedef struct Edge
{int u,v,d;bool operator < (const struct 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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！