题目描述(ID:12287)
标题: 单行道问题
标签: 图结构
详情:
在某个城市有n个著名的风景点,风景点之间通过一些单行道和双行道进行连接。游客无论从哪个风景点出发,都可以沿着这些道路到达其他任何一个风景点。但是随着游客越来越多,交通事故也逐渐增加。因为单行道显然比双行道要安全得多,所以市长决定把尽可能多的双行道改成单行道,以减少事故的发生。刚好今年的JSOI比赛就在该市举行,而你是参赛选手之一,于是市长决定把这个任务交给你来完成。
现在你的任务就是调整这个城市的交通系统,把尽可能多的双行道改造成单行道,并确定它们的方向。要注意的是你不能改变原有单行道的方向,也不能另外新建一些道路,还必须保证经过改造的交通系统仍然能够让游客在任何两个风景点之间往返。
输入格式:
输入第一行是两个数n,m,2<=n<=200,n-1<=m<=n(n-1)/2;其中n是风景点的数目,m是所有当行道和双行道的总数目。
以下m行每行有3个数a,b,c。1<=a<=n,1<=b<=n,a<>b,c=1或者2。如果c=1,则表示有一条从a到b的单行道;如果c=2,则表示a和b之间有一条双行道。任意两个风景点之间至多有一条道路。
输出格式:
需要改造的双行道的数目。
样例:

输入

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

输出

1
登录并解答