求关键割边……话说最近在跟andy同学的题～～

先求出来最小割，然后从src开始一次floodfill，如果u->v还有剩余容量，那么就从u转移到v；然后从sink一次floodfill，如果u->v还有剩余容量，就从v转移到u。

如果说有一条边u->v，并且u只在第一次floodfill被访问到（也就是说能从src到达u并且u不能到达sink，且v能到达sink且src不能到达v，也就是说从s到t经过u、v的这条路只被边u->v给阻塞，那么显然增大u->v的容量就可以增加流量）。

建图：

s到每个project一条Xi的边，每个employee到t一条Yi的边。

如果project_i需要employee_j，那么project_i到employee_j一条inf的边。

把钱看作流，本来project_i能获得Xi的钱，但是其中有一部分流到了employee_j，然后被employee_j消耗掉了（实际上是从employee_j流向了t，可以看作是被employee_j吃掉了），显然按照这样构图，employee_j只能吃一次，刚好符合题意。

如果求完最大流以后，从s->v的弧没有了剩余容量，说明要么v得到的钱还不够他的employee吃的，要么刚好够他的employee吃的，

最小割点集。

v拆点为v1、v2，之间连容量为1的弧，每条路径上的容量都是inf，要注意的是最终的pasture到sink的时候，是pasture拆出来的p1连接sink而不是p2连接sink因为可能会有超过1的流到达p1，如果用p2连接sink的话，最大流就会偏小（当然，p1、p2之间连一条inf也是可以的）

最后求从barn到sink的最大流即可。

另外，发现我写的isap跟andy同学的isap效率差别很是巨大……交上去TLE对着他的代码看了半天没看出哪儿错了，最后找来数据一跑发

最小割唯一性判断。

正向一次最大流，然后从s开始flood_fill，如果u->v之间有一条未饱和的弧，就从u fill到v。

反向一次最大流，然后从t开始flood_fill。

如果两次floodfill遇到的点集的交集为空，并集为全集则有唯一最小割。

zoj的数据貌似有问题。。capacity可以是0，理论上来讲，如果给所有的正向弧的cap都增加1求出来的结果应该是一样的，但是zoj上如果给cap都加1就会wa掉。

老鼠跑到我的可乐瓶子里面（小老鼠）。。然后我就把瓶子盖上……各种折磨最终给玩死……

希望不会做噩梦。。也希望母老鼠不要来报复……

= =

简单对暑假集训结束后的机房进行一个总结

注：本帅是普通队员，无头衔，所以这是非官方总结——当然，如果是官方的总结也不会来找我来写，如果您期待着看到官方总结，请关注[http://hi.baidu.com/blackstar08][http://hi.baidu.com/ericxieforever]。

按人来～

首先是小灰越同学 自打

首先如果当作一个回路来做的话，就会越想越麻烦，实际上，在返回的时候，可以把所有经过的边都反向，这样就变成了从1到N走两次，不走同一条边，使得两次长度之和最短。

如果两次长度一样，那显然是一个简单的网络流，但是现在的问题在于长度不一样，不过分析一下就会发现，如果把长度看作cost，那么刚好是一个费用流……

但是我们只需要走两次，所以添加超级源s和超级汇t，从s到1一条费用为0容量为2的边，从N到t一条费用为0容量为2的边，其余都是费用为其长度，容量为1的边，最后求一个最小费用。

做这个题

一开始用Java写 无限RE。最后终于狠下心来用C++重写了一遍 果然过了= = 无比悲伤。。

可以看作是一个模板题，有关于算法细节请移步：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.6687&rep=rep1&type=pdf

不知道效率如何。

虽然改了以后匹配有点贪心思想，但是就算匹配的不是最优的，随后的增广操作会修正这次不够优的匹配，所以最后应该能求出最优解。

二分图的多重匹配。

修改了下HK算法，但是修改后的这个算法很可能是错误的。

HK本身是用一个一维数组来记录每个点所匹配的那个点，我修改成了用2维数组来记录每个点匹配的那些点，在bfs的时候尚容易对应过来，但是在dfs的时候原来的算法非常容易理解，修改后就有了一些贪心思想（优先直接匹配，如果不能直接匹配才会考虑增广，我之所以不知道算法的正确性就在于对增广的理解太过肤浅）。

至于range。。其实直接暴力也能过（2秒8左右（Java的时限是3倍）），

rt。干了些啥未知。估计他也没能进我系统，毕竟有密码

（我2点05离开的本子）

日志名称:          System
来源:            Microsoft-Windows-Power-Troubleshooter
日期:            2010/8/29 15:32:54
事件 ID:         1
任务类别: