首页 > > 程序设计 > C/C++ >

1003 电话连线

2018-06-17 22:49:51来源：未知阅读 ()

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

分类标签 Tags 点此展开

裸prim但是我上来就智障的敲了个kruskal也是醉了

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 struct node
  7 {
  8     int u;
  9     int v;
 10     int w;
 11 }edge[10001];
 12 struct ans
 13 {
 14     int x;
 15     int y;
 16 }a[10001];
 17 int num=1;
 18 int f[1001];
 19 int cmp(const node &a,const node &b)
 20 {
 21     return a.w<b.w;
 22 }
 23 int find(int x)
 24 {
 25     if(x!=f[x])
 26     f[x]=find(f[x]);
 27     return f[x];
 28 }
 29 void unionn(int x,int y)
 30 {
 31     int fx=find(x);
 32     int fy=find(y);
 33     f[fx]=fy;
 34 }
 35 int comp(const ans &a,const ans &b)
 36 {
 37     if(a.y>b.y)return 1;
 38     if(a.y==b.y&&a.x<b.x)return 1;
 39     return 0;
 40 }
 41 int now=1;
 42 int main()
 43 {
 44     int n;
 45     scanf("%d",&n);
 46     for(int i=1;i<=n;i++)f[i]=i;
 47     for(int i=1;i<=n;i++)
 48     {
 49         for(int j=1;j<=n;j++)
 50         {
 51             int p;
 52             scanf("%d",&p);
 53             if(j>i)
 54             {
 55                 edge[num].u=i;
 56                 edge[num].v=j;
 57                 edge[num].w=p;
 58                 num++;
 59             }
 60         }
 61     }
 62     sort(edge+1,edge+num,cmp);
 63     int k=0;
 64     int tot=0;
 65     int feiyong=0;
 66     for(int i=1;i<=num;i++)
 67     {
 68         if(find(edge[i].u)!=find(edge[i].v))
 69         {
 70             unionn(edge[i].u,edge[i].v);
 71             //printf("%d %d\n",edge[i].u,edge[i].v);
 72             if(edge[i].w!=0)
 73             {
 74                 tot++;
 75                 feiyong=feiyong+edge[i].w;
 76                 //ans1[now]=edge[i].u;
 77                 //ans2[now]=edge[i].v;
 78                 a[now].x=min(edge[i].u,edge[i].v);
 79                 a[now].y=max(edge[i].u,edge[i].v);
 80                 k++;
 81                 now++;
 82             }
 83             
 84         }
 85         if(k==n-1)break;
 86     }
 87     /*for(int i=1;i<=now;i++)
 88     {
 89         for(int j=i;j<=now;j++)
 90         {
 91             if(ans1[j]>ans1[j+1])
 92             {
 93                 swap(ans1[j],ans1[j+1]);
 94                 swap(ans1[j],ans2[j+1]);
 95             }
 96         }
 97     }*/
 98     sort(a+1,a+now,comp);
 99     printf("%d\n",tot);
100     for(int i=1;i<=now-1;i++)
101     {
102         printf("%d %d\n",a[i].x,a[i].y);
103     }
104     printf("%d",feiyong);
105     return 0;
106 }

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 const int MAXN = 105;
 5 const int INF = 2147483647;
 6 int i, j, n;
 7 long long ans = 0;
 8 int edge[MAXN][MAXN], key[MAXN], p[MAXN], vis[MAXN] = {0}, //edge表示存的边 key表示权值，p表示父亲，vis表示是否已经存在已生成的树中
 9         f[MAXN], l[MAXN], m = 0; //f表示头，右边表示尾
10 int main() {
11     cin >> n;
12     for(i = 1; i <= n; i++)for(j = 1; j <= n; j++) cin >> edge[i][j];
13     for(i = 1; i <= n; i++) key[i] = INF;
14     key[1] = 0; //
15     p[1] = 1;
16     int Mini, Min;
17     for(i = 0; i < n; i++) { //之需要加最多n条边，故循环n次
18         Min = INF;
19         for(j = 1; j <= n; j++) if(!vis[j] && key[j] < Min) {
20                 Mini = j;    //找key值最小的点，即与树相邻的节点的最小权值边
21                 Min = key[j];
22             }
23         vis[Mini] = 1; //设置访问过，即生成树已连接Mini这个节点
24         ans += key[Mini];
25         if(key[Mini]) {
26             f[m] =   min(p[Mini], Mini); //字典序的边
27             l[m++] = max(p[Mini], Mini); //同上
28         }
29         for(j = 1; j <= n; j++) //伪松弛，更新树临边节点的key值并维护p域
30             if(!vis[j] && edge[Mini][j] < key[j]) {
31                 key[j] = edge[Mini][j];
32                 p[j] = Mini;
33             }
34     }
35     cout << m << endl;
36     for(i = 0; i < m; i++) cout << f[i] << ' ' << l[i] << endl;
37     cout << ans;
38     return 0;
39 }