题目描述

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

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

 

 

题解

• 我们可以发现让其余所有边都减1和让自己加1没什么区别

   

• 考虑kruskal的过程，首先边权大于这条边的是不用考虑的

   

• 考虑把那些边权比这条边小的调节到比这条边大，这样就相当于在生成树上去掉了这条边

   

• 至于调大到多少自然是使得边权恰好大1

   

• 让这条边必然存在就一定得让这条边链接的两个点不连通，于是我们把在生成树上去掉这条边看成割断这条边，于是这就是一个最小割

 

代码

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 const int N=1010; 7 queue
         
           Q; 8 struct edge{
   int to,from,w;}e[N*4]; 9 struct node{
   int u,v,w,o;}E[N];10 int n,m,S,T,k,t,cnt=1,ans,head[N],d[N],cur[N];11 int cmp(node a,node b) { return a.w==b.w?a.o