带权边通路最小长度，直接Kruskal即可
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int M=5000; const int N=110; struct edge{ int u,v,w; }edges[M]; int pre[N]; int find(int i){ return pre[i]==i?i:pre[i]=find(pre[i]); } int cmp(edge a,edge b){ return a.w<b.w; } int kruskal(int n,int m){ int ans=0; for(int i=1;i<=n;i++) pre[i]=i; sort(edges+1,edges+m+1,cmp); for(int i=1;i<=m;i++){ int x=find(edges[i].u); int y=find(edges[i].v); if(x!=y){ ans+=edges[i].w; pre[x]=y; } } return ans; } int main(){ int n,m; while(~scanf("%d",&n)&&n){ for(int i=1;i<=n*(n-1)/2;i++){ scanf("%d %d %d",&edges[i].u,&edges[i].v,&edges[i].w); } int ans=kruskal(n,n*(n-1)/2); printf("%d\n",ans); } }