HDU 1879 继续畅通工程

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1879
还是最小生成树的模板题
我用的Prim算法
View Code
 1 #include<stdio.h>
 2  #include<string.h>
 3  int map[110][110],lowcost[110],visit[110];
 4  #define N 1000000
 5  int prim(int maxminum)
 6  {
 7      int i,sum,j,k,min;
 8      for(i=1;i<=maxminum;i++)
 9      {
10          lowcost[i]=map[1][i];
11          visit[i]=0;
12      }
13      sum=0;
14      visit[1]=1;
15      for(i=1;i<maxminum;i++)
16      {
17          min=N;
18          for(j=1;j<=maxminum;j++)
19          {
20              if(visit[j]==0&&lowcost[j]<min)
21              {
22                  min=lowcost[j];
23                  k=j;
24              }
25          }
26         
27          if(min==N)
28          break;
29    visit[k]=1;
30          sum+=min;
31          for(j=1;j<=maxminum;j++)
32          {
33              if(visit[j]==0&&map[k][j]<lowcost[j])
34              {
35                  lowcost[j]=map[k][j];
36              }
37          }
38      }
39      return sum;
40  }
41  int main()
42  {
43      int maxmax,maxminum,i,a,b,value,sum,flag;
44      while(~scanf("%d",&maxminum))
45      {
46          if(maxminum==0)
47          break;
48          memset(map,N,sizeof(map));
49          maxmax=(maxminum*(maxminum-1))/2;
50    for(i=1;i<=maxminum;i++)
51              map[i][i]=0;
52          for(i=1;i<=maxmax;i++)
53          {
54              scanf("%d%d%d%d",&a,&b,&value,&flag);
55     if(flag==0)
56              {
57      if(value<map[a][b])
58              {
59                  map[a][b]=map[b][a]=value;
60              }
61     }
62     else
63     {
64      map[a][b]=map[b][a]=0;
65     }
66          }
67          sum=prim(maxminum);
68          printf("%d\n",sum);
69      }
70      return 0;
71  }