网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[Tyvj Aug11]冗余电网
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | ugrid.in | 输出文件 | ugrid.out |
TYVJ八月月赛提高组第2题
测试点数目:5
测试点分值:20
--内存限制:128M
--时间限制:1s
测试点数目:5
测试点分值:20
--内存限制:128M
--时间限制:1s
【题目描述】
北冰洋有一座孤岛,多年来一直没电。近日,令岛民们振奋的消息传来:S国的专家要为他们修建电网!!!
孤 岛上共有N个村庄,发电站要建在第K个村庄中。S国的专家要在N个村庄间修建M条输电线路,但由于地理原因,M条线路无法保证每个村庄都与第K个村庄(建 有发电站)直接相连,同样,也不一定能保证每个村庄都与第K个村庄间接相连(假设A与B直接相连,B与C直接相连,那么A与C间接相连)。
然而,由于S国的专家智商实在太“高”了,以至于设计出了许多冗余线路。现给出第i条线路两个端点Ui,Vi(分别表示线路连接的两个村庄,Ui!=Vi)和长度Li,请你帮岛民算一下:如果电网可以覆盖全岛,最少需要多长的电线;若不能,有多少个村庄无电可用。
注意:0<=冗余线路数目
孤 岛上共有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
具体含义见题目描述
接下来M行:Ui Vi Li
具体含义见题目描述
【输出格式】
如果电网可以覆盖全岛,输出最少需要的电线长度;
若不能,输出无电可用的村庄的个数。
【样例输入】
【样例1】 5 5 1 1 2 1 2 3 1 3 4 1 4 5 1 5 1 1 【样例2】 5 5 1 1 2 1 1 2 2 1 2 3 3 4 1 5 4 2
【样例输出】
【样例1】 4 【样例2】 3
【提示】
样例解释:
对于样例一,电网可以覆盖全岛,最短长度为4;
对于样例二,电网无法覆盖3,4,5这3个村庄。
数据范围:
对于20%的数据,有1
【来源】
From tbcaaa8 http://www.tyvj.cn/Problem_Show.aspx?id=1591