【bzoj3624】[Apio2008]免费道路

2015年4月24日2,6710

Description

Input

Output

Sample Input

5 7 2
1 3 0
4 5 1
3 2 0
5 3 1
4 3 0
1 2 1
4 2 1
 

Sample Output

3 2 0
4 3 0
5 3 1
1 2 1

题解

优先加1做生成树,得出必须添加的0的边

反过来,将0的边加至K条,再放1的边