[清华集训2012] 最小生成树
题目描述
给定一个边带正权的连通无向图 $G=(V,E)$,其中 $N=|V|,M=|E|$,$N$ 个点从 $1$ 到 $N$ 依次编号,给定三个正整数 $u,v$ 和 $L(u\ne v)$,假设现在加入一条边权为 $L$ 的边 $(u,v)$,那么需要删掉最少多少条边,才能够使得这条边既可能出现在最小生成树上,也可能出现在最大生成树上?
输入输出格式
输入格式
第一行包含用空格隔开的两个整数,分别为 $N$ 和 $M$;
接下来 $M$ 行,每行包含三个正整数 $u,v$ 和 $w$ 表示图 $G$ 存在一条边权为 $w$ 的边 $u,v$。
最后一行包含用空格隔开的三个整数,分别为 $u,v$ 和 $L$;
数据保证图中没有自环。
输出格式
输出一行一个整数表示最少需要删掉的边的数量。
输入输出样例
输入样例 #1
3 2
3 2 1
1 2 3
1 2 2
输出样例 #1
1
说明
#### 样例解释
我们只需把边 $(1,2)$ 删除即可,删除并加入新边之后,图中的生成树唯一。
#### 数据规模与约定
对于 $20\%$ 的数据满足 $N\leqslant10,M\leqslant20,L\leqslant20$;
对于 $50\%$ 的数据满足 $N\leqslant300,M\leqslant3000,L\leqslant200$;
对于 $100\%$ 的数据满足 $N\leqslant20000,M\leqslant200000,L\leqslant20000$。