prim 1003 电话连线

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<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 int a[1000][1000];
 6 int dis[1000];
 7 int maxn=9999999;
 8 int n;
 9 int path[1000];
10 int x[1000][2];
11 void scan();
12 void prim();
13 int main()
14 {
15     scan();
16     prim();
17     return 0;
18 }
19 void scan()
20 {
21     cin>>n;
22     for(int i=1;i<=n;i++)
23      {
24          for(int j=1;j<=n;j++)
25           {
26               cin>>a[i][j];
27           }
28      }
29 }
30 int vis[1000];
31 int minn;
32 
33 void prim()
34 {
35     int cnt=0;
36     for(int i=1;i<=n;i++)
37      {
38          dis[i]=maxn;
39      }
40      dis[1]=0;
41      int u;
42      int ans=0;
43      for(int i=1;i<=n;i++)
44       {
45           minn=maxn;
46           for(int j=1;j<=n;j++)
47          {
48              if(dis[j]<minn&&vis[j]==0)
49              {
50                  minn=dis[j];
51                u=j;    
52             }
53          }    
54       
55       ans+=minn;
56       vis[u]=1;
57       for(int j=1;j<=n;j++)
58        {
59            if(dis[j]>a[u][j]&&vis[j]==0)
60             {
61                 dis[j]=a[u][j];
62                 path[j]=u;
63             }
64        }
65        
66        if(minn)  
67         {  
68            x[cnt][0]=min(path[u],u);  
69            x[cnt][1]=max(path[u],u);  
70            cnt++;  
71         }  
72         }
73        printf("%d
",cnt);  
74        for(int i=0;i<cnt;i++)  
75        {  
76         printf("%d %d
",x[i][0],x[i][1]);  
77        }  
78        printf("%d
",ans); 
79 }