Problem 2005 --小伍当老板

2005: 小伍当老板

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $104$ 正确数量 $18$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 图论 并查集

小伍同学当上了老板,并计划在他的公司建立一个新的网络。共有N台电脑,它们可以使用网线相互连接。由于公司的每个工作人员都必须访问整个网络,所以每台电脑必须可以通过任何其他电脑(可能有一些中间电脑)的网线接入网络中。 
由于小伍经费不足,所以有必要制定一个计划,使得网线总长度最小,但是由于位置的限制,有些电脑是不可能直接连到一块的。下面给出所有可以连接的电脑对及其距离。

输入的第一行包含两个整数:n(2<=n<=100):代表电脑总数,编号从1到n。m(1<=m<=1500):代表接下来有m行。

接来下每行三个整数,u,v,w

代表u和v是可以连接的并且距离为w

首先输出需要的网线总长度,然后按编号顺序输出需要连接的电脑对。特别说明:

对于:

3 3

1 2 1

2 3 2

1 3 2

输出

3

1 2

1 3

相信你已经明白了我的意思

4 6
1 2 1
1 3 1
1 4 3
2 4 4
2 3 1
3 4 2
4
1 2
1 3
3 4

不要用普里姆算法,用克鲁斯卡尔

推荐代码 查看2005 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$0 $ms] 槑槑 479562 2019-10-05 14:36:58
内存最少[$1220 $KB] 陈世雄@网络工程151 110771 2017-07-09 20:45:35
第一AC 陈善如@计算机142 110744 2017-07-09 19:33:36
第一挑战 刘欢@计算机科学与技术161 110726 2017-07-09 18:38:27

赛题来源/所属竞赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛
1108 ACM暑期集训:训练9 2017-07-09 18:30:00 请登录