首页 > 题解 > bzoj 2521 [Shoi2010]最小生成树

bzoj 2521 [Shoi2010]最小生成树

Description

Secsa最近对最小生成树问题特别感兴趣。他已经知道如果要去求出一个n个点、m条边的无向图的最小生成树有一个Krustal算法和另一个Prim的算法。另外,他还知道,某一个图可能有多种不同的最小生成树。例如,下面图 3中所示的都是图 2中的无向图的最小生成树:

当然啦,这些都不是今天需要你解决的问题。Secsa想知道对于某一条无向图中的边AB,至少需要多少代价可以保证AB边在这个无向图的最小生成树中。为了使得AB边一定在最小生成树中,你可以对这个无向图进行操作,一次单独的操作是指:先选择一条图中的边 P1P2,再把图中除了这条边以外的边,每一条的权值都减少1。如图 4所示就是一次这样的操作:

Input

输入文件的第一行有3个正整数n、m、Lab分别表示无向图中的点数、边数、必须要在最小生成树中出现的AB边的标号。
接下来m行依次描述标号为1,2,3…m的无向边,每行描述一条边。每个描述包含3个整数x、y、d,表示这条边连接着标号为x、y的点,且这条边的权值为d。
输入文件保证1<=x,y<=N,x不等于y,且输入数据保证这个无向图一定是一个连通图。

Output

输出文件只有一行,这行只有一个整数,即,使得标号为Lab边一定出现最小生成树中的最少操作次数。

Sample Input

4 6 1

1 2 2

1 3 2

1 4 3

2 3 2

2 4 4

3 4 5

Sample Output

1

HINT

第1个样例就是问题描述中的例子。

1<=n<=500,1<=M<=800,1<=D< 10^6

题解

操作相当于对一个边+1。

我们发现只要别的边的大小比这条边还大的话,那就不需要考虑它的影响了。

如果想排除某条边的干扰,显然让他的权值比给定边恰好大1是最优的选择。

所以我们可以把所有小于等于他权值的边加入网络流的图中,权值改为wid(给定边的权值)-当前边的权值+1,然后以给定边的两个端点为起点终点跑最大流求最小割即可,因为我们需要求最小的代价使给定边的两个端点不联通。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×