數據-最小生成樹

最小生成樹

Description

　給定一個邊帶正權的連通無向圖G=(V,E)，其中N=|V|，M=|E|，N個點從1到N依次編號，給定三個正整數u，v，和L (u≠v)，假設現在加入一條邊權為L的邊(u,v)，那麼需要刪掉最少多少條邊，才能夠使得這條邊既可能出現在最小生成樹上，也可能出現在最大生成樹上？

Input

　　第一行包含用空格隔開的兩個整數，分別為N和M；
接下來M行，每行包含三個正整數u，v和w表示圖G存在一條邊權為w的邊(u,v)。
最後一行包含用空格隔開的三個整數，分別為u，v，和 L；
數據保證圖中沒有自環。
Output

　輸出一行一個整數表示最少需要刪掉的邊的數量。

Sample Input

3 2
3 2 1
1 2 3
1 2 2
Sample Output

1

最佳回答：

http://hzwer.com/3666.html