当前位置:首页 > 生成树 > 正文
SSOJ2439局域网
314+

题目大意:计算机之间连接这很多网线,有些网线是多余,如两台计算机已经可以联通,就不需要再用网线连接他们,现给出每个网线的畅通程度,请去掉多余的网线,并让整个网络最畅通。

题目描述

某个局域网内有n(n<=100)台计算机,由于搭建局域网时工作人员的疏忽,现在局域网内的连接形成了回路,我们知道如果局域网形成回路,那么数据将不停的在回路内传输,造成网络卡的现象。因为连接计算机的网线本身不同,所以有一些连线不是很畅通,我们用f(i,j)表示i、j之间连接的畅通程度(f(i,j)<=1000),f(i,j)值越小表示i,j之间连接越畅通,f(i,j)为0表示i、j之间无网线连接。现在我们需要解决回路问题,我们将出去一些连线,使得网络中没有回路,并且被出去网线的∑f(i,j)最大,请求出这个最大值。

输入

第一行两个正整数n、k。

接下来的k行每行三个正整数i,j,m,表示i,j两台计算机之间有网线连通,畅通程度为m。

输出

一个正整数,∑f(i,j)的最大值。

样例输入

5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2

样例输出

8

解题思路

这是典型的最小生成树题目,保留畅通程度小的网线,去掉畅通值大的多余网线。可以先把网线按畅通值从小到大排序,一根一根地使用,如果网线连接的两台计算机已经联通,则他是多余的,否则他是要连线的。把多余网线的畅通值累加起来即是答案。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,,,

SSOJ2439局域网:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter