#P3204. Ikki's Story I - Road Reconstruction
Ikki's Story I - Road Reconstruction
描述
Ikki 是一个小国凤凰(Phoenix)的国王。凤凰国非常小,只有一座城市负责生产日常用品,并通过道路网络将这些货物运输到首都。Ikki 发现国家面临的最大问题是运输速度太慢。
由于 Ikki 曾是一名 ACM/ICPC 竞赛选手,他意识到这实际上是一个最大流问题。他编写了一个最大流程序并找到了当前的最大运输能力。然而,他对当前的运输速度并不满意,因此希望提高国家的运输能力。方法相对简单:Ikki 可以重建运输网络中的某些道路,使这些道路能够承载更高的运输容量。但遗憾的是,凤凰国的 GDP 并不充裕,只能承担重建一条道路的费用。Ikki 需要找到那些一旦重建就能提高整个网络运输能力的道路。
他思考这个问题很久却无法解决,于是将问题交给了 frkstyc,而 frkstyc 将其放入了本次 POJ Monthly 竞赛中。你能帮 Ikki 解决这个问题吗?
输入
输入包含恰好一个测试用例。
测试用例的第一行包含两个整数 和 (,),分别表示凤凰国的城市数量和道路数量。
接下来 行,每行包含三个整数 、、,表示存在一条从城市 到城市 的道路,其运输容量为 (,)。所有道路均为有向。
城市编号从 到 ,生产货物的城市编号为 ,首都编号为 。
输出
输出一行,仅包含一个整数 ,表示有 条道路满足:重建任意一条都能提高网络的最大运输能力。
输入样例 1
2 1
0 1 1
输出样例 1
1
来源
POJ 月赛—2007.03.04,由 Ikki 命题