题目描述 Description
一个国家有n个城市。若干个城市之间有电话线连接，现在要增加m条电话线（电话线当然是双向的了），使得任意两个城市之间都直接或间接经过其他城市有电话线连接，你的程序应该能够找出最小费用及其一种连接方案。
输入描述 Input Description
输入文件的第一行是n的值（n<=100）.
第二行至第n+1行是一个n*n的矩阵，第i行第j列的数如果为0表示城市i与城市j有电话线连接，否则为这两个城市之间的连接费用（范围不超过10000）。
输出描述 Output Description
输出文件的第一行为你连接的电话线总数m，第二行至第m+1行为你连接的每条电话线，格式为i j，（i<j）， i j是电话线连接的两个城市。输出请按照Prim算法发现每一条边的顺序输出，起始点为1.
第m+2行是连接这些电话线的总费用。
样例输入 Sample Input
5
0 15 27 6 0
15 0 33 19 11
27 33 0 0 17
6 19 0 0 9
0 11 17 9 0
样例输出 Sample Output
2
1 4
2 5
17
数据范围及提示 Data Size & Hint
n<=100
/*
Prim求最小生成树
lowcost记录当前要想到达该点所需的最小消耗
son记录前驱，便于输出
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#define M 101
#define INF 10000000
using namespace std;
int map[M][M],vis[M],lowcost[M],son[M],xx[M*M],yy[M*M],n,ans,tot;
int main()
{
memset(map,0x7f,sizeof(map));
int x;
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
scanf("%d",&x);
if(x>)map[i][j]=x;
else if(i!=j)map[i][j]=;
}
int pos=;
vis[]=;
for(int i=;i<=n;i++)
if(i!=pos)
{
son[i]=;
lowcost[i]=map[i][pos];
}
for(int i=;i<n;i++)
{
int minn=INF;
for(int j=;j<=n;j++)
{
if(!vis[j]&&lowcost[j]<minn)
{
pos=j;
minn=lowcost[j];
}
}
ans+=minn;
vis[pos]=;
if(lowcost[pos])
{
xx[++tot]=min(pos,son[pos]);
yy[tot]=max(pos,son[pos]);
}
for(int j=;j<=n;j++)
if(!vis[j]&&lowcost[j]>map[pos][j])
{
lowcost[j]=map[pos][j];
son[j]=pos;
} }
printf("%d\n",tot);
for(int i=;i<=tot;i++)
printf("%d %d\n",xx[i],yy[i]);
printf("%d",ans);
return ;
}