1003 电话连线

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 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

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

1 4

2 5

数据范围及提示 Data Size & Hint

n<=100

 1 #include<cstdio>
 2 #include<cstring>
 3 const int N=101;
 4 const int inf=9999999;
 5 int map[N][N];
 6 int minn[N];
 7 bool vis[N];
 8 int fa[N];  
 9 int que[N];
10 int n,ans,cnt;
11 int main()
12 {
13     scanf("%d",&n);
14     for(int i=1;i<=n;++i)
15     {
16         for(int j=1;j<=n;++j)
17         {
18             int x;
19             scanf("%d",&x);
20             map[i][j]=x;
21         }
22     }
23     for(int i=1;i<=n;++i)
24     {
25         minn[i]=map[1][i];
26         fa[i]=1;
27     }
28     vis[1]=1;
29     for(int i=1;i<n;++i)
30     {
31         int a=inf,k;
32         for(int j=1;j<=n;++j)
33             if(!vis[j]&&minn[j]<a)
34             {
35                 a=minn[j];
36                 k=j;
37                 que[cnt]=j;
38             }
39         ans+=a;
40         vis[k]=1;
41         if(a!=0 && a!=inf) cnt++; 
42         for(int j=1;j<=n;++j)
43         {
44             if(vis[j]==0&&(map[k][j]<minn[j]))
45             {
46                 minn[j]=map[k][j];
47                 fa[j]=k;
48             }
49         }
50     }
51     printf("%d
",cnt);
52     for(int i=0;i<cnt;++i)
53     {
54         if(fa[que[i]]<que[i])printf("%d %d
",fa[que[i]],que[i]);
55         else printf("%d %d
",que[i],fa[que[i]]);
56     }
57     printf("%d",ans);    
58     return 0;
59 }