最小生成树
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
生成最小树
题目限制
1000 ms 256 M
题目描述
你有一个含n个点,m条边的图。现在选出一棵生成树,你每次可以选择树上一条边使其边权-1,问至少需要操作多少次之后这棵树会成为图的最小生成树?保证图完全连通且不含重边。
注:图中节点编号从1 ~ n。
输入格式
第一行输入两个数n,m,分别表示图的点数和边数;(1≤n≤10000,1≤m≤100000) 之后m行,每行三个数u,v,w,表示从点u到点v的连边权值为w; 之后n-1行,每行两个数a,b,表示选定生成树的每条边。
输出格式
输出一个数,表示最少的操作次数。
数据范围
对于25%的数据,1≤n≤20,1≤m≤100;
对于40%的数据,1≤n≤100,1≤m≤500;
对于60%的数据,1≤n≤1000,1≤m≤5000;
对于100%的数据,1≤n≤10000,1≤m≤100000,1≤w≤1000000,1≤a,b
输入样例
5 7
1 2 5
1 3 3
1 4 1
1 5 2
2 3 2
3 4 4
4 5 7
2 3
3 1
1 4
4 5
输出样例
5
样例解释
样例中的情况如图所示,对于选定的树,只要将4--5的边的权值改为2即可成为最小生成树,操作次数为5。
NOIP模拟赛1
- Status
- Done
- Rule
- OI
- Problem
- 4
- Start at
- 2022-11-12 8:00
- End at
- 2022-11-12 12:00
- Duration
- 4 hour(s)
- Host
- Partic.
- 37