題目描述 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=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&x);
if(x>0)map[i][j]=x;
else if(i!=j)map[i][j]=0;
}
int pos=1;
vis[1]=1;
for(int i=1;i<=n;i++)
if(i!=pos)
{
son[i]=1;
lowcost[i]=map[i][pos];
}
for(int i=1;i<n;i++)
{
int minn=INF;
for(int j=1;j<=n;j++)
{
if(!vis[j]&&lowcost[j]<minn)
{
pos=j;
minn=lowcost[j];
}
}
ans+=minn;
vis[pos]=1;
if(lowcost[pos])
{
xx[++tot]=min(pos,son[pos]);
yy[tot]=max(pos,son[pos]);
}
for(int j=1;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=1;i<=tot;i++)
printf("%d %d\n",xx[i],yy[i]);
printf("%d",ans);
return 0;
} View Code