最优布线问题

【问题描述】

  学校有n台计算机,为了方便数据传输,现要将它们用数据线连接起来。两台计算机被连接是指它们间有数据线连接。由于计算机所处的位置不同,因此不同的两台计算机的连接费用往往是不同的。

    当然,如果将任意两台计算机都用数据线连接,费用将是相当庞大的。为了节省费用,我们采用数据的间接传输手段,即一台计算机可以间接的通过若干台计算机(作为中转)来实现与另一台计算机的连接。

  现在由你负责连接这些计算机,任务是使任意两台计算机都连通(不管是直接的或间接的)。

【输入格式】

  输入文件wire.in,第一行为整数n(2<=n<=100),表示计算机的数目。此后的n行,每行n个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。

【输出格式】

  输出文件wire.out,一个整数,表示最小的连接费用。

【输入样例】

  3

  0 1 2

  1 0 1

  2 1 0

【输出样例】

    2   (注:表示连接1和2,2和3,费用为2)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int maxn=0x7fffffff;
 6 int map[101][101];
 7 int minn[101];
 8 int vis[101];
 9 int vis2[101][101];
10 int main()
11 {
12     int n,m;
13     scanf("%d%d",&n,&m);
14     for(int i=0;i<=n;i++)minn[i]=maxn;
15     for(int i=0;i<=n;i++)
16     for(int j=0;j<=n;j++)
17     {
18         if(i==j)
19         map[i][j]=0;
20         else
21         map[i][j]=maxn;
22     }
23     for(int i=1;i<=m;i++)
24     {
25         int x,y,z;
26         scanf("%d%d%d",&x,&y,&z);
27         map[x][y]=z;
28         map[y][x]=z;
29     }
30     for(int i=1;i<=n;i++)
31     {
32         if(map[1][i])
33         minn[i]=map[1][i];
34     }
35     minn[1]=0;
36     vis[1]=1;
37     int now=1;
38     for(int i=2;i<=n;i++)
39     {
40         int k=0;
41         for(int j=2;j<=n;j++)
42         {
43             if(vis[j]==0&&minn[j]<minn[k])
44             {
45                 k=j;
46             }
47         }
48         vis[k]=1;
49         //printf("%d %d\n",now,k);
50         now=k;
51         for(int j=2;j<=n;j++)
52         {
53             if(vis[j]==0&&map[k][j]<minn[j])
54             {
55                 minn[j]=map[k][j];
56             }
57         }
58     }
59     int tot=0;
60     for(int i=1;i<=n;i++)
61     tot=tot+minn[i];
62     printf("%d\n",tot);
63     for(int i=1;i<=n;i++)
64     {
65         for(int j=1;j<=n;j++)
66         {
67             if(map[i][j]==minn[i]&&vis2[i][j]==0&&i!=j)
68             {
69                 vis2[i][j]=1;
70                 vis2[j][i]=1;
71                 printf("%d %d\n",j,i);
72             }
73         }
74     }
75     return 0;
76 }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏wincent的专栏

SPEED 飞车扩容改造:敢于对过去说不

接手飞车运维以来,在扩缩容上耗费了比较多的精力,于是有了我们今天的主题,飞车扩容改造。

2321
来自专栏蓝天

mooon-agent设计要点

mooon-agent以简约的设计为主,力求各对象之间保持简单的关系,尽量避免过度的传递,因此CAgentThread成了核心。除此之外,还有几个关键的设计点:

952
来自专栏FreeBuf

自动化沙箱打造之“关于XShell我有话说”

最近XShell很是火了一把,每个安全厂商都在发通告,都在分析,反正就是百花齐放,在这里我想做一个总结,从前些时间的勒索软件到今天的xshell,其实我们可以看...

3306
来自专栏架构师小秘圈

cdn技术原理

作者:IT世界,来自:www.it.com.cn 1. 前言   Internet的高速发展,给人们的工作和生活带来了极大的便利,对Internet的服务品质和...

1.3K9
来自专栏FreeBuf

通过USB调试攻击固件安装后门以实现“邪恶女佣”攻击

调试机制是帮助跟踪几乎所有平台上的故障源的标准组件。一般主要在平台生产之前使用,但也经常用于翻新和修复返回的平台。安全研究人员可以多次使用调试特性测试攻击,包括...

1124
来自专栏小文博客

带有3D翻转书特效的WordPress图片企业主题

1602
来自专栏纯洁的微笑

电商平台备战促销季的运维秘诀——高可用服务层

1202
来自专栏BeJavaGod

RabbitMQ 一二事(4) - 路由模式介绍

路由模式其实和订阅模式差不多,只不过交换机的类型不同而已 ? 路由模式可以用下图来表示,比订阅模式多了一个key,举个栗子就是根据不同的人群来订阅公众号,来收取...

3385
来自专栏GA小站

Google Analytics数据保护政策变更解读(201804)

相信很多管理员一大早就收到一封谷歌分析的关于数据保存和数据保护协议变更的通知邮件,有些人就问,这会不会对Clientid,Userid有什么影响,或对我们有什么...

752
来自专栏微信公众号:Java团长

我的编码习惯 —— 日志规范

开发中日志这个问题,每个公司都强调,也制定了一大堆规范,但根据实际情况看,效果不是很明显,主要是这个东西不好测试和考核,没有日志功能一样跑啊。

992

扫码关注云+社区

领取腾讯云代金券