题目链接：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 lowcost[maxn],closet[maxn],vis[maxn]; int prim(int n)// 复杂度O(n^2) n为顶点数 { int ans=0,num=0; for(int i=1;i<=n;i++) { lowcost[i]=c[1][i]; closet[i]=1; } vis[1]=1; for(int i=2;i<=n;i++) { int mn=INF; int pos=1; for(int k=2;k<=n;k++) if(lowcost[k]<mn&&!vis[k]) { mn=lowcost[k]; pos=k; } if(mn==INF)return -1; vis[pos]=1; ans+=mn; for(int k=2;k<=n;k++) // 将pos点引入集合后 ， 计算其他不在集合内的点到“集合”的距离 if(c[pos][k]<lowcost[k]&&!vis[k]) { lowcost[k]=c[pos][k]; closet[k]=pos; } } return ans; } int main() { int n,m; while(~scanf("%d%d",&n,&m)&&n) { memset(vis,0,sizeof(vis)); for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) c[i][j]=INF+1; for(int i=0;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); c[u][v]=w; c[v][u]=w; } int ans=prim(m); if(ans==-1) printf("?\n"); else printf("%d\n",ans); } }