#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 解决这个问题吗?

输入

输入包含恰好一个测试用例

测试用例的第一行包含两个整数 NNMMN500N \leq 500M5,000M \leq 5,000),分别表示凤凰国的城市数量和道路数量。

接下来 MM 行,每行包含三个整数 aabbcc,表示存在一条从城市 aa 到城市 bb 的道路,其运输容量为 cc0a,b<n0 \leq a, b < nc100c \leq 100)。所有道路均为有向

城市编号从 00n1n-1,生产货物的城市编号为 00,首都编号为 n1n-1

输出

输出一行,仅包含一个整数 KK,表示有 KK 条道路满足:重建任意一条都能提高网络的最大运输能力

输入样例 1

2 1
0 1 1

输出样例 1

1

来源

POJ 月赛—2007.03.04,由 Ikki 命题