bzoj#P2861. 双向边定向为单向边

双向边定向为单向边

题目描述

A 国由 nn 个城市,mm 条道路组成,两个城市之间,可能存在一条或多条道路,可能是单行道,也可能是双行道。

现在你要把尽量多的双行道定向,改成单行道,并且保证连通性不变。

所谓连通性不变,就是如果原本 A 城市可以到 B 城市。那么道路改造之后 A 仍然能够到 B 城市。

输入格式

第一行两个整数 n,mn,m

接下来 mm 行,每行三个整数 u,v,cu,v,c。若 cc11 则表示存在一条 uvu\to v 的单行道,否则存在一条连接 u,vu,v 的双行道。

输出格式

一行一个整数 kk,表示至多可以在满足条件的情况下给 kk 条双行道定向。

4 4
1 2 1
2 3 2
3 1 2
2 4 2
2

数据规模与约定

对于 100%100\% 的数据,1n1051\leq n\leq 10^51m2×1051\leq m\leq 2\times 10^51uvn1\leq u\not = v\leq n