程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 更多編程語言 >> 編程解疑 >> 數據-最小生成樹

數據-最小生成樹

編輯:編程解疑
最小生成樹

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved