Chinaunix首页 | 论坛 | 博客
  • 博客访问: 506072
  • 博文数量: 65
  • 博客积分: 1158
  • 博客等级: 少尉
  • 技术积分: 1261
  • 用 户 组: 普通用户
  • 注册时间: 2012-07-18 22:07
文章分类

全部博文(65)

文章存档

2016年(1)

2014年(2)

2013年(9)

2012年(53)

分类: C/C++

2012-10-31 16:09:34

/*
Description 
John是一个农场主,他有几个牧场,为了好好照顾他的牛,他必须在几个牧场之间来回,可糟糕的天气往往使得道路非常泥泞,为此John准备在牧场之间铺一些石子路,这样在下雨天也能快速地从一个牧场到另外一个牧场。但John的资金有限,为了自己能从任一个牧场都通过石子路到达另外一个牧场,他需要好好设计一下线路。请帮助John设计好线路,使得John能从任一个牧场都通过石子路到达另外一个牧场,且线路的费用最低。


输入:

第一行是一个整数K,表示有多少个测试用例,以后每个测试用例占n+1行。每个测试用例的第一行为一个整数n(3<=n<=20),表示有多少个牧场,从第二行开始为一个n*n的矩阵,矩阵元素aij表示从i个牧场到j个牧场的铺路费用。


输出:

每行输出一个测试用例的最小铺路费用。
 
  
Sample Input  
2
6
0 6 1 5 0 0
6 0 5 0 3 0
1 5 0 5 6 4
5 0 5 0 0 2
0 3 6 0 0 6
0 0 4 2 6 0
4
0 1 2 3
1 0 3 4
2 3 0 1
3 4 1 0 
  
Sample Output  
15
*/


点击(此处)折叠或打开

  1. # include <stdio.h>


  2. int findMinimumCost(int input[21][21],int n);//这里[][]必须有下标

  3. int main(void)
  4. {
  5.     int cases,n,i,j,input[21][21],minimumCost;

  6.     scanf("%d",&cases);

  7.     while(cases--)
  8.     {
  9.         scanf("%d",&n);

  10.         for(i=1;i<=n;i++)
  11.         {
  12.             for(j=1;j<=n;j++)
  13.             {
  14.                 scanf("%d",&input[i][j]);
  15.                     if( 0 == input[i][j] )
  16.                     {
  17.                         input[i][j] = 9999999;
  18.                     }
  19.             }
  20.         }

  21.         minimumCost = findMinimumCost(input,n);
  22.         printf("%d\n",minimumCost);
  23.     }
  24.     
  25.     return 0;
  26. }

  27. int findMinimumCost(int input[21][21],int n)
  28. {
  29.     bool mark[21];
  30.     int k,j,m,lowestCost[21],minimumCost,min;

  31.     minimumCost = 0;
  32.     mark[1] = true;

  33.     for(k=2;k<=n;k++)
  34.     {
  35.         lowestCost[k] = input[1][k];
  36.         mark[k] = false;
  37.     }

  38.     for(k=1;k<n;k++)
  39.     {
  40.         min = 9999999;
  41.         j = 1;

  42.         for(m=2;m<=n;m++)
  43.         {
  44.             if( lowestCost[m] < min && !mark[m] )
  45.             {
  46.                 min = lowestCost[m];
  47.                 j = m;
  48.             }
  49.         }
  50.         mark[j] = true;
  51.         minimumCost += min;
  52.         
  53.         for(m=2;m<=n;m++)
  54.         {
  55.             if( input[j][m] < lowestCost[m] && !mark[m] )
  56.             {
  57.                 lowestCost[m] = input[j][m];
  58.             }
  59.         }
  60.     }

  61.     return minimumCost;


  62. }

阅读(713) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~