本文共 1075 字，大约阅读时间需要 3 分钟。
#include#include #include using namespace std;struct Edge{ int from, to, w; int next;};int tol, n, m,u,v,w,cop,sum;int head[105];int id[105];Edge edges[10005];//根据顶点估计边数 完全图这里 用有向表示无向 故有n*(n-1) 最多大约 10000 bool cmp(const Edge &a, const Edge &b){ return a.w < b.w;}void addEdge(int from, int to, int w){ edges[tol].next = head[from]; edges[tol].from = from; edges[tol].to = to; edges[tol].w = w; head[from] = tol++;}int find(int p){ if(p == id[p]) return p; else return id[p] = find(id[p]);}int main() { int i, j; while(scanf("%d%d",&m, &n) == 2){ if(m == 0) break; tol = 0; cop = n; sum = 0; for(i = 0; i <= n;++i) id[i] = i; for(i = 0; i < m; ++i){ scanf("%d%d%d",&u,&v,&w); addEdge(u,v,w); } sort(edges,edges+m,cmp);//按照权重从小到大排序 for(int i = 0; i < m; ++i){ int p = find(edges[i].from); int q = find(edges[i].to); if(p == q) continue; sum += edges[i].w; id[p] = q; --cop;//记录连通分量 } if(cop > 1){//如果不能连通所有即 连通分量大于1 printf("?\n"); continue; } printf("%d\n",sum); } return 0; }
转载地址：http://smimi.baihongyu.com/