bzoj#P2861. 双向边定向为单向边
双向边定向为单向边
题目描述
A 国由 个城市, 条道路组成,两个城市之间,可能存在一条或多条道路,可能是单行道,也可能是双行道。
现在你要把尽量多的双行道定向,改成单行道,并且保证连通性不变。
所谓连通性不变,就是如果原本 A 城市可以到 B 城市。那么道路改造之后 A 仍然能够到 B 城市。
输入格式
第一行两个整数 。
接下来 行,每行三个整数 。若 为 则表示存在一条 的单行道,否则存在一条连接 的双行道。
输出格式
一行一个整数 ,表示至多可以在满足条件的情况下给 条双行道定向。
4 4
1 2 1
2 3 2
3 1 2
2 4 2
2
数据规模与约定
对于 的数据,,,。