hdoj 1863 最小生成树之畅通工程

畅通工程

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

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

这题是简单的最小生成树问题一次AC

第一次做这种题目用prim算法不过也稍微纠结了一下后来才知道i<m 呵呵

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <queue>
 4 using namespace std;
 5 #define  max  101
 6 int p[max][max],f[max],dist[max];
 7 const int INTMAX=1<<30;
 8 int m,n;
 9 
10 void init()
11 {
12     for (int i=0;i<=max;i++)
13         for (int j=0;j<=max;j++)
14                     p[i][j]=INTMAX;
15 }
16 
17 int prim()
18 {
19     int i,min=INTMAX;
20     int j;
21     int sum=0,v=1;
22     for (i=1;i<=m;i++)
23     {
24         dist[i]=p[v][i];
25         f[i]=0;
26     }
27     f[1]=1;
28     //dist[v]=max;
29     for (i=1;i<m;i++)
30     {
31         min=INTMAX;
32         for (j=1;j<=m;j++)
33             if (!f[j]&&min>dist[j])
34                 min=dist[v=j];            
35         if (min==INTMAX)
36             return -1;
37         sum+=min;
38         f[v]=1;
39         for (j=1;j<=m;j++)
40                     if (!f[j]&&dist[j]>p[v][j])
41                         dist[j]=p[v][j];    
42     }
43     return sum;
44 }
45 
46 int main()
47 {
48     int a,b,i,c;
49     while(cin>>n>>m&&n)
50     {
51         init();
52         for (i=0;i<n;i++)
53         {
54             cin>>a>>b>>c;
55             if (p[a][b]>c)
56                             p[a][b]=p[b][a]=c;            
57         }
58         int k;
59         k=prim();
60         if (k==-1)
61         printf("?\n");
62         else
63             printf("%d\n",k);
64     }
65     return 0;
66 }