【bzoj2229】[Zjoi2011]最小割

2015年1月28日4,1637

Description

小白在图论课上学到了一个新的概念——最小割,下课后小白在笔记本上写下了如下这段话: “对于一个图,某个对图中结点的划分将图中所有结点分成两个部分,如果结点s,t不在同一个部分中,则称这个划分是关于s,t的割。 对于带权图来说,将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量,而s,t的最小割指的是在关于s,t的割中容量最小的割” 现给定一张无向图,小白有若干个形如“图中有多少对点它们的最小割的容量不超过x呢”的疑问,小蓝虽然很想回答这些问题,但小蓝最近忙着挖木块,于是作为仍然是小蓝的好友,你又有任务了。

Input

输入文件第一行有且只有一个正整数T,表示测试数据的组数。 对于每组测试数据, 第一行包含两个整数n,m,表示图的点数和边数。 下面m行,每行3个正整数u,v,c(1<=u,v<=n,0<=c<=106),表示有一条权为c的无向边(u,v) 接下来一行,包含一个整数q,表示询问的个数 下面q行,每行一个整数x,其含义同题目描述。

Output

对于每组测试数据,输出应包括q行,第i行表示第i个问题的答案。对于点对(p,q)和(q,p),只统计一次(见样例)。

两组测试数据之间用空行隔开。

Sample Input

1
5 0
1
0

Sample Output

10

【数据范围】
对于100%的数据 T<=10,n<=150,m<=3000,q<=30,x在32位有符号整数类型范围内。
图中两个点之间可能有多条边

题解

fhq神犇题解:

首先,注意这样一个事实:如果(X,Y)是某个s1-t1最小割,(Z,W)是某个s2-t2最小割,那么X∩Z、X∩W、Y∩Z、Y∩W这四项不可能均非空。也就是说,最小割不可能相互跨立。

这个蕴含了,最多一共有N-1个不同的s-t最小割。只需把这些割找出来即可。

寻找的方法:首先,在V中任意找两个点a,b,求最大流,把V划分为割X-Y,之后对X、Y分别递归地进行划分。这样就能得到N-1个割了。

 

  • Chenyao2015年1月30日 上午10:51 回复

    Orzzzzzz

    #1  
  • 婷小葵葵葵2015年7月22日 下午8:45 回复

    请问那个事实和得出的结论有什么关系…任意一个A+B=S的划分形式都具有那个性质吧…但可能有2^|S|划分啊…

    #2  
  • Lvat_s2016年4月30日 上午2:43 回复

    黄学长您好……请问restore中直接除以2会不会导致答案错误……这样有可能有些容量为奇数边的容量减少1……

    #3  
    • 梦奇地2016年4月30日 下午12:18 回复

      在这儿是无向图嘛,一条边和其反向边的残量加起来是一定是这条边容量的二倍咯,除以二就可以得到原来的容量啦。

      (这种写法也可以说是巧妙也可以说是懒咯)

      #31
      • hzwer2016年5月1日 下午11:20 回复
        admin

        是这样的

        #32
  • gzz2017年3月28日 上午11:16 回复

    求fhq神犇讲解地址
    btw,那个结论我好像举出反例了怎么办233

    #4