HDU-1863 畅通工程

应用了prim算法模板，一下子就过了。

畅通工程

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 13084 Accepted Submission(s): 5358

Problem Description

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。

Input

测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N
行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。

Output

对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。

Sample Input

3 3

1 2 1

1 3 2

2 3 4

1 3

2 3 2

0 100

Sample Output

3

?

Source

浙大计算机研究生复试上机考试-2007年

Recommend

lcy

 1 #include<stdio.h>
 2 #define max 10000000
 3 int  map[101][101],visit[101];
 4 int length[101];
 5 int getmin(int n)
 6 {
 7       int i,min;
 8     for(i=1;i<=n;i++)
 9     {
10         if(visit[i]==0)
11         {
12             min=i;
13             break;
14         }
15     }
16    for(i++;i<=n;i++)
17    {
18        if(visit[i]==0&&length[min]>length[i])
19              min=i;
20    }
21       return min;
22 }
23 int prim(int n)
24 {
25     int i,j;
26     int min;
27     int sum;
28     for(i=1;i<=n;i++)
29     {
30         visit[i]=0;
31         length[i]=map[1][i];
32     }
33        visit[1]=1;
34          sum=0;
35      for(i=2;i<=n;i++)
36      {
37          min=getmin(n);
38          visit[min]=1;
39          sum+=length[min];
40          for(j=1;j<=n;j++)
41          {
42              if(visit[j]==0)
43              {
44                  if(map[min][j]<length[j])
45                  {
46                      length[j]=map[min][j];
47                  }
48              }
49          }
50      }
51      return sum;
52 }
53 int main()  
54 {  
55     int n, m;  
56     int i,j;  
57     int min;  
58     int u, v, cost;  
59     while (~scanf("%d%d",&m,&n)&&m!=0)  
60     {  
61        for(i=1;i<=n;i++)
62           for(j=1;j<=n;j++)
63                 map[i][j]=max;
64         for (i = 0; i <= n; i++)  
65             map[i][i] = 0;  
66         for (i = 0;i<m;i++)  
67         {  
68             scanf("%d%d%d", &u, &v,&cost);  
69                 map[u][v] = cost;  
70                 map[v][u] = cost; 
71         } 
72           min = prim(n);
73         if(min>=max)
74             printf("?
");
75         else
76           printf("%d
",min);  
77     }
78     return 0;
79 }

用了浓缩的prim的模板，出错了，却怎么也找不到什么错误。

#include<stdio.h>
#include<string.h>
#define MAX 100000
int map[101][101],v[101];
int prim(int n)//最好的prim的模板。
{
    int k[510],i,j;
    int min,sum=0,flag,count=1;
    memset(k,0,sizeof(k));
    memset(v,0,sizeof(v));
    for(i=1;i<=n;i++)
        k[i]=map[1][i];
    for(i=2;i<=n;i++)
    {
        min=MAX;
        for(j=2;j<=n;j++)
        {
            if(min>k[j]&&v[j]==0)
            {
                min=k[j];
                flag=j;
            }
        }
        sum+=min;
        v[flag]=1;
        for(j=1;j<=n;j++)
            if(v[j]==0&&k[j]>map[flag][j]&&flag!=j)
                k[j]=map[flag][j];
    }
  return sum;
}
int main()
{
   int n,m,i,j,p,q,r,min;
   while(~scanf("%d%d",&m,&n)&&m!=0)
    {
       for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                if(i==j) map[i][j]=0;
                else 
                    map[i][j]=MAX;
            }
            for(i=0;i<m;i++)
            {
                scanf("%d%d%d",&p,&q,&r);
                map[p][q]=map[q][p]=r;
            }
        min=prim(n);//调用出错了。怎么改？
      if(min>=MAX)
      printf("?
");
      else
        printf("%d
",min);
    }
    return 0;
}