hdu 1233 - 还是畅通工程

时间：2014-03-09 01:33:53 阅读：455 评论：0 收藏：0 [点我收藏+]

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 22297 Accepted Submission(s): 9961

Problem Description

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

Input

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。

Output

对每个测试用例，在1行里输出最小的公路总长度。

Sample Input

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

Sample Output

3 5

Hint Huge input, scanf is recommended.

Source

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

题解：

求解最小生成树。

   1:  #include<stdlib.h>

   2:  #include<stdio.h>

   3:  #include<string.h>

   4:  #define INF 10000001

   5:  #define maxn 101

   6:  int map[maxn][maxn];

   7:  int cost[maxn];

   8:  int chosed[maxn];

   9:  int count;

  10:  long total_cost;

  11:  void init_map(int n){

  12:      int i,j;

  13:      for(i=1;i<=n;i++)

  14:          for(j=1;j<=n;j++)

  15:              map[i][j]=(i==j?0:INF);

  16:  }

  17:  void init(int n){

  18:      int i;

  19:      memset( chosed , 0 , sizeof(chosed));

  20:      chosed[1]=1;

  21:      count=1;

  22:      for( i = 1 ; i <= n ; i++ )

  23:          cost[i] = map[1][i];

  24:  }

25:

  26:  void prim(int n){

  27:      int min,min_idx;

  28:      int i;

  29:      total_cost=0;

  30:      while( count <=n ){

  31:          min = INF;

  32:          for( i = 2 ; i <= n ; i++ ){

  33:              if( !chosed[i] && cost[i] < min){

  34:                  min_idx=i;

  35:                  min=cost[i];

  36:              }

  37:          }

  38:          if( min == INF )

  39:              return;

  40:          chosed[min_idx]=1;

  41:          total_cost+=min;

  42:          count++;

  43:          for( i = 1 ; i <= n ; i++)

  44:              if(!chosed[i]&& map[min_idx][i]<cost[i])

  45:                  cost[i] = map[min_idx][i];

  46:      }

  47:  }

48:

  49:  int main(){

  50:      int road,node,i;

  51:      while(scanf("%d",&node)!=EOF&& node ){

  52:          road=(node-1)*node/2;

  53:          init_map(node);

  54:          count=0;

  55:          while(road--){

  56:              int a,b,c;

  57:              scanf("%d %d %d",&a,&b,&c);

  58:              map[a][b]=c;

  59:              map[b][a]=c;

  60:          }

  61:          init(node);

  62:          prim(node);

  63:          printf("%ld\n",total_cost);

  64:      }

  65:  }

原文：http://www.cnblogs.com/ZJUT-jiangnan/p/3588729.html

踩

(0)

评论一句话评论（0）

分享档案

更多>