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
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 { for(j=0;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 { min= Infinity; key = 0; for(j=1;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 { if(!flag[j]&&cost[key][j]!=0&&cost[key][j] lowcost[j] = cost[key][j]; } i++; } cout< } return 0; }