1003 电话连线

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

分类标签 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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏码匠的流水账

聊聊rocketmq的PushConsumerImpl

io/openmessaging/rocketmq/consumer/PushConsumerImpl.java

1772
来自专栏小樱的经验随笔

HDU 2438 Turn the corner(三分查找)

托一个学弟的福,学了一下他的最简便三分写法,然后找了一道三分的题验证了下,AC了一题,写法确实方便,还是我太弱了,漫漫AC路!各路大神,以后你们有啥好的简便写法...

2925
来自专栏xingoo, 一个梦想做发明家的程序员

Spark MLlib 之 aggregate和treeAggregate从原理到应用

由于treeAggregate是在aggregate基础上的优化版本,因此先来看看aggregate是什么.

1340
来自专栏HansBug's Lab

3891: [Usaco2014 Dec]Piggy Back

3891: [Usaco2014 Dec]Piggy Back Time Limit: 10 Sec  Memory Limit: 128 MB Submit:...

3729
来自专栏分布式系统进阶

Influxdb中Select查询请求结果涉及到的一些数据结构

相当于c里面的链表元素,itr指向下一个元素的指针,buf表示当前元素,即FloatPoint类型的链表的迭代器.

1602
来自专栏函数式编程语言及工具

Akka(8): 分布式运算:Remoting-远程查找式

  Akka是一种消息驱动运算模式,它实现跨JVM程序运算的方式是通过能跨JVM的消息系统来调动分布在不同JVM上ActorSystem中的Actor进行运算,...

4269
来自专栏技术之路

WPF MVVM实现TreeView

今天有点时间,做个小例子WPF MVVM 实现TreeView 只是一个思路大家可以自由扩展 文章最后给出了源码下载地址 图1 ?    图2     ? 模...

2679
来自专栏码匠的流水账

聊聊jesque的WorkerImpl与WorkerPool

Resque是一个使用redis来创建后台任务的ruby组件。而jesque是其java版本。通常用来做延时队列。

731
来自专栏拂晓风起

jQuery 和 json 简单例子(注意callback函数的处理!!) (servlet返回json,jquery更新,java json)

1163
来自专栏逆向与安全

菜鸟 学注册机编写之 “RSA”

选取两个别人不知道的大素数p, q. 公共模n = p*q 欧拉值φ(n) = (p-1)(q-1) 选取公匙(加密匙) e , 条件是1< e <φ(n...

1790

扫码关注云+社区

领取腾讯云代金券