题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1863
#include<cstdio> #include<queue> #include<iostream> #include<vector> #include<map> #include<cstring> #include<string> #include<set> #include<stack> #include<algorithm> #define cle(a) memset(a,0,sizeof(a)) #define inf(a) memset(a,0x3f,sizeof(a)) #define ll long long #define Rep(i,a,n) for(int i=a;i<=n;i++) using namespace std; const int INF = ( 2e9 ) + 2; const int maxn = 110; int c[maxn][maxn]; int prim(int n) { int lowcost[maxn],closet[maxn],vis[maxn]; int ans=0; for(int i=2;i<=n;i++) { lowcost[i]=c[1][i]; closet[i]=1; } memset(vis,0,sizeof(vis)); vis[1]=1; for(int i=2;i<=n;i++) { int pos=0,mn=INF; for(int k=2;k<=n;k++) if(lowcost[k]<mn&&!vis[k]) { mn=lowcost[k]; pos=k; } ans+=mn; vis[pos]=1; for(int k=2;k<=n;k++) if(lowcost[k]>c[pos][k]&&!vis[k]) { lowcost[k]=c[pos][k]; closet[k]=pos; } } return ans; } int main() { int n; while(~scanf("%d",&n)&&n) { int m=n*(n-1)/2; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) c[i][j]=INF+1; for(int i=0;i<m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); c[u][v]=w; c[v][u]=w; } printf("%d\n",prim(n)); } }