| 题目名称 | 1215. [Tyvj Aug11] 冗余电网 |
|---|---|
| 输入输出 | ugrid.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 5 |
| 题目来源 |
 Makazeu
于2012-10-24加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：95， 提交：280， 通过率：33.93% | ||||
 +1s |
100 | 0.051 s | 1.34 MiB | C++ |
|
+1s |
100 | 0.053 s | 3.34 MiB | C++ |
 xxcxcxcx |
100 | 0.077 s | 1.50 MiB | C++ |
 syzhaoss |
100 | 0.079 s | 2.98 MiB | C++ |
 雾茗 |
100 | 0.134 s | 7.69 MiB | C++ |
|
xxcxcxcx |
100 | 0.141 s | 2.79 MiB | C++ |
|
锝镆氪锂铽 |
100 | 0.146 s | 6.60 MiB | C++ |
 cool |
100 | 0.160 s | 0.82 MiB | C++ |
 white |
100 | 0.162 s | 3.34 MiB | C++ |
 subarashii |
100 | 0.162 s | 4.10 MiB | C++ |
| 本题关联比赛 | |||
| 图论练习和一些常规题 | |||
| 图论练习和一些常规题 | |||
| 关于 冗余电网 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
快读秒一切
+1s
2018-02-06 16:06
6楼
| ||||
|
。。。233
 洛克索耶夫
2016-03-12 09:32
5楼
| ||||
|
普里姆不行啊，找根都很难，数据中有回路的……最后学了神犇的结构体才过……（bgm17）
 浮生随想
2016-02-20 08:30
4楼
| ||||
|
居然被find函数坑了。。。。。
f[x]=find(f[x])写成x=find(f[x]); 居然只有一个点不过。。。默默地吐槽一下这渣数据。。。  Sky_miner
2016-02-18 10:43
3楼
| ||||
|
回复 @新的风暴已经现 :
sb，没过题就不要秀代码  乌龙猹
2014-10-16 07:15
2楼
| ||||
|
最小生成树+一个判断，奇怪为什么这么长时间都没人过、、、
注意： 1.开long long 2.数据范围200000 | ||||
【题目描述】
北冰洋有一座孤岛，多年来一直没电。近日，令岛民们振奋的消息传来：S国的专家要为他们修建电网！！！
岛上共有N个村庄，发电站要建在第K个村庄中。S国的专家要在N个村庄间修建M条输电线路，但由于地理原因，M条线路无法保证每个村庄都与第K个村庄(建有发电站)直接相连，同样，也不一定能保证每个村庄都与第K个村庄间接相连(假设A与B直接相连，B与C直接相连，那么A与C间接相连)。
然而，由于S国的专家智商实在太“高”了，以至于设计出了许多冗余线路。现给出第i条线路两个端点Ui,Vi(分别表示线路连接的两个村庄,Ui!=Vi)和长度Li，请你帮岛民算一下：如果电网可以覆盖全岛，最少需要多长的电线；若不能，有多少个村庄无电可用。注意：0<=冗余线路数目
【输入格式】
第一行：N,M,K。
接下来M行：Ui,Vi,Li,具体含义见题目描述。
【输出格式】
如果电网可以覆盖全岛，输出最少需要的电线长度；
若不能，输出无电可用的村庄的个数。
【输入样例1】
5 5 1 1 2 1 2 3 1 3 4 1 4 5 1 5 1 1
【输出样例1】
4
【输入样例2】
5 5 1 1 2 1 1 2 2 1 2 3 3 4 1 5 4 2
【输出样例2】
3
【样例解释】
对于样例一，电网可以覆盖全岛，最短长度为4;
对于样例二，电网无法覆盖3,4,5这3个村庄。
【数据范围】
对于20%的数据，1<n,m<=10;
对于60%的数据，1<n,m<=1000;
对于100的数据，1<=n,m<=200000,1<=li<=10^7;
对于40的数据，电网无法覆盖全岛。
【题目来源】
TYVJ八月月赛提高组第2题 http://www.tyvj.cn/Problem_Show.aspx?id=1591