【整理中】最大流

4
12
2013

【整理中】最大流

黑色已过

网络流：

基础

poj1149: 给你一堆猪圈，以及一些买猪的人，每个买猪的人操作时可以打开一些猪圈，他最多买走一定数量的猪。最后，在他操作结束后，可以任意移动已经打开的猪圈里面的猪，关上猪圈，继续下一个人。问最多能卖多少猪。

sol：

考虑每次交易和所有猪圈构成网格，去除多余的节点，得到：

S->第一个在这个猪圈买猪的人，容量是这个猪圈猪的数量。合并冗余的边。

如果一个猪圈一共有n次交易，则第i个顾客往i+1连一条边。

顾客往T连一条容量为购买限制的边。

hdu1569: m是列n是行……

带上下界的网络流

无源无汇带上下界网络流：
- 求出一组解，使得对于任意一条边满足C(u,v)∈[L,R]，ΣC(u,v) - ΣC(v,p) = 0
- sgu194：给n个点，及m根pipe，每根pipe用来流躺液体的，单向的，每时每刻每根pipe流进来的物质要等于流出去的物质，要使得m条pipe组成一个循环体，里面流躺物质。并且满足每根pipe一定的流量限制，范围为[Li,Ri].即要满足每时刻流进来的不能超过Ri(最大流问题)，同时最小不能低于Li。
- sol:先把每条边的容量Ri-Li，也就是强制流入Li。
- 重新计算每个点的入流量-出流量
- 显然，如果一个点的入流量!=出流量，就需要在Li的基础上加上delta。
- 为了分配delta，一个显然的事实就是，通过一个超级源给入流量>出流量的点，入流量-出流量的流入，（也就是在满流的情况下将会全部从这里流出去，这样出流量就平衡了）
- 同理，给入流量<出流量的点，出流量-入流量的流出空间到超级汇
有源有汇带上下界网络流：
- 求出一组解，是的对除了S和T以外的点，满足以上流量守恒性质
- zoj3229 Shoot the Bullet：一个屌丝给m个女神拍照，计划拍照n天，每一天屌丝最多个C个女神拍照，每天拍照数不能超过D张，而且给每个女神i拍照有数量限制[Li，Ri]，对于每个女神n天的拍照总和不能超过Gi，如果有解求屌丝最多能拍多少张照，并求每天给对应女神拍多少张照；否则输出-1。
- 加入T到S的一条容量无穷大的边，同上面方法做，加入新源汇SS,TT，然后去掉这条边和SS,TT，再跑一次S到T的最大流。
- 引用：当有可行流时，删除超级源点ss和超级终点dd，再对（s，d）进行一次最大流，此时得到的maxflow则为题目的解。为什么呢？因为第一次maxflow（）只是求得所有满足下界的流量，而残留网络（s，d）路上还有许多自由流（没有和超级源点和超级汇点连接的边）没有流满，所有最终得到的maxflow=（第一次流满下界的流+第二次能流通的自由流）。
可行流、最小费用可行流：
- 如果只要可行流，则不需要第二次操作。
- 如果要最小费用，则第二次操作增广时，出现正数停止。
- zju2314 sgu176