a205. APIO2008 2.免费道路 - 高中生程式解題系統

內容

新亚（New Asia）王国有N 个村庄，由M 条道路连接。其中一些道路是鹅
卵石路，而其它道路是水泥路。保持道路免费运行需要一大笔费用，并且看上去
王国不可能保持所有道路免费。为此亟待制定一个新的道路维护计划。
国王已经决定保持尽可能少的道路免费，但是每两个不同的村庄之间都应该
由一条且仅由一条免费道路的路径连接。同时，虽然水泥路更适合现代交通的需
要，但国王也认为走在鹅卵石路上是一件有趣的事情。所以，国王决定保持刚好
K 条鹅卵石路免费。

举例来说，假定新亚王国的村庄和道路如图3(a)所示。如果国王希望保持两
条鹅卵石路免费，那么可以如图3(b)中那样保持道路(1, 2)、(2, 3)、(3, 4)和(3, 5)
免费。该方案满足了国王的要求，因为：(1)每两个村庄之间都有一条由免费道
路组成的路径；(2)免费的道路已经尽可能少；(3)方案中刚好有两条鹅卵石道路
(2, 3)和(3, 4)。

图3: (a)新亚王国中村庄和道路的一个示例。实线标注的是水泥路，虚线标注
的是鹅卵石路。(b)一个保持两条鹅卵石路免费的维护方案。图中仅标出了免
费道路。

给定一个关于新亚王国村庄和道路的描述以及国王决定保持免费的鹅卵石
道路数目，写一个程序确定是否存在一个道路维护计划以满足国王的要求，如果
存在则任意输出一个方案。

輸入說明

输入第一行包含三个由空格隔开的整数：
N，村庄的数目(1≤N≤20,000)；
M，道路的数目(1≤M≤100,000)；
K，国王希望保持免费的鹅卵石道路数目(0≤K≤N - 1)。
此后M 行描述了新亚王国的道路，编号分别为1 到M。第(i+1)行描述了第i 条
道路的情况。用3 个由空格隔开的整数描述：
ui 和vi，为第i 条道路连接的两个村庄的编号，村庄编号为1 到N；
ci，表示第i 条道路的类型。ci = 0 表示第i 条道路是鹅卵石路，ci = 1 表
示第i 条道路是水泥路。
输入数据保证一对村庄之间至多有一条道路连接。

輸出說明

如果满足国王要求的道路维护方案不存在，你的程序应该在输出第一行打印no solution。
否则，打印yes。

範例輸入 #1

範例輸出 #1

yes

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (5%): 1.0s , <1K
不公開測資點#1 (5%): 1.0s , <1K
不公開測資點#2 (5%): 1.0s , <1K
不公開測資點#3 (5%): 1.0s , <1M
不公開測資點#4 (5%): 1.0s , <1M
不公開測資點#5 (5%): 1.0s , <1M
不公開測資點#6 (10%): 1.0s , <1M
不公開測資點#7 (10%): 1.0s , <1M
不公開測資點#8 (10%): 1.0s , <10M
不公開測資點#9 (10%): 1.0s , <10M
不公開測資點#10 (10%): 1.0s , <1K
不公開測資點#11 (10%): 1.0s , <1K
不公開測資點#12 (10%): 1.0s , <1K

提示：

样例中，若选择
3 2 0
4 3 0
5 3 1
1 2 1
这几条边即可满足题意。

原题是Special Judge，十分麻烦，于是将题目改为只输出是否有解即可。

由于测资简单，故不公开，敬请见谅。

如对测资有疑问，欢迎提出！

感谢morris1028补上图片！

標籤:

出處:

APIO 2008 第二题 [管理者： liouzhou_101 (王启圣) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」