ACM John的農場（最小生成樹） C++實現

         John的農場

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

4

#include<iostream>

using namespace std;

#define Infinity 65535

bool flag[21];

int  cost[21][21],lowcost[21],mincost;

int main()

{

 int k;

 cin>>k;

 while(k--)

 {

  int n;

  cin>>n;

  int i,j;

  mincost = 0;

  memset(flag,false,sizeof(flag));

  memset(lowcost,0,sizeof(lowcost));

  for(i=0;i<n;i++)

  {

   for(j=0;j<n;j++)

   {

       cin>>cost[i][j];

    if(cost[0][i]!=0)

    {

      lowcost[i]=cost[0][i];

    }

    else lowcost[i]=Infinity;

   }

  }

  flag[0]=true;

  i=0;

  int key;

  int min;

  while(i<n-1)

  {

   min= Infinity;

   key = 0;

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

   {

    if(!flag[j]&&lowcost[j]!=0&&min>lowcost[j])

    {

     min = lowcost[j];

     key = j;

    }

   }

   flag[key] = true;

   mincost+=lowcost[key];

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

   {

    if(!flag[j]&&cost[key][j]!=0&&cost[key][j]<lowcost[j])

     lowcost[j] = cost[key][j];

   }

   i++;

  }

  cout<<mincost<<endl;

 }

 return 0;

}