hdu1233浙大计算机研究生复试上机考试(2006)还是畅通工程 - 果冻虾仁
hdu1233浙大计算机研究生复试上机考试(2006)还是畅通工程
还是畅通工程
当N为0时,输入结束,该用例不被处理。
3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0
3 5Huge input, scanf is recommended.HintHint
#include <iostream> using namespace std; const int MAX=5500; const int INF = 0x3f3f3f3f; int cost[MAX][MAX]; int sum; void prim(int n,int v) { int lowcost[MAX],min; int i,j,k; for(i=1;i<=n;i++) { lowcost[i]=cost[v][i]; } for(i=1;i<n;i++) { min=INF; for(j=1;j<=n;j++) if(lowcost[j]!=0&&lowcost[j]<min) { min=lowcost[j]; k=j; } sum+=min; lowcost[k]=0; for(j=1;j<=n;j++) if(cost[k][j]!=0&&cost[k][j]<lowcost[j]) { lowcost[j]=cost[k][j]; } } } int main() { int n; while(scanf("%d",&n)) { if(!n) break; sum=0; int t=n*(n-1)/2; for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) if(i==j) cost[0][0]=0; int v,h,d; while(t--) { scanf("%d%d%d",&v,&h,&d); cost[v][h]=d; cost[h][v]=d; } prim(n,1); printf("%d\n",sum); } return 0; }