HDU 1879 还是prim最小生成树、

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<string.h>
 4 const int qq=100+10,MAX=1e7;
 5 int vis[qq];
 6 int lowcost[qq][qq];
 7 int minimum[qq];
 8 int n;
 9 void prim()
10 {
11             int minx,k;
12             int sum=0;
13             vis[1]=1;
14             for(int i=0;i<=n+1;++i)
15                 minimum[i]=lowcost[1][i];
16             for(int i=1;i<n;++i){
17                 minx=MAX;
18                 for(int j=1;j<=n;++j)
19                     if(!vis[j] && minx > minimum[j]){
20                         minx=minimum[j];
21                         k=j;
22                     }
23                 vis[k]=1;
24                 sum+=minx;
25                 for(int l=1;l<=n;++l)
26                     if(!vis[l] && minimum[l] > lowcost[k][l])
27                         minimum[l]=lowcost[k][l];
28             }
29             printf("%d\n",sum);
30 }
31 int main()
32 {
33     while(~scanf("%d",&n)&&n){
34         for(int i=0;i<=n+1;++i)
35             minimum[i]=MAX;
36         for(int j,i=0;i<=n+1;++i)
37             for(j=0;j<=n+1;++j)
38                 lowcost[i][j]=MAX;
39         for(int i=0;i<=n+1;++i)
40             vis[i]=0;
41         int i,j,cost,mark;
42         for(int l=1;l<=n*(n-1)/2;++l){
43             scanf("%d %d %d %d",&i,&j,&cost,&mark);
44             if(mark==1){
45                 lowcost[i][j]=lowcost[j][i]=0;            //已经存在路径的话直接权值为0 
46             }
47             else
48                 lowcost[i][j]=lowcost[j][i]=(i==j)?0:cost;
49         }
50         prim();
51     }
52 }