初识网络流

    最近开始学网络流了，原来或多或少接触过最简单的最大流问题：

    一个公路网，每条公路都有一定的车载上限，问整个网络最大的车流量是多少。这个问题可以形式化为：

定义：给有向图G中的每一条弧(u,v)赋予一个值f(u,v)，并规定两个点s和t。如果除了s，t外的任意一个节点i，都有sum{f(u,i)}=sum{f(i,v)}。那么我们说f是一个流，并把s成为源(source)，t称为汇(sink)。并把上式称为流量平衡条件。

 

最大流问题   

    求有向图G中的一个流，它满足容量限制条件f(u,v)<=c(u,v)，且源点提供的流尽量大。

 

最小割最大流定理（重难点）

    s-t最大流的流值等于s-t的最小切割容量。证明略去。一般模型隐蔽的比较深。

 

最小费用最大流

    有向图G的边除了满足容量限制外，每条边也有费用，在最大流的基础上，求出费用和最小的的最大流。

 

有上下界的最大流(最小流)问题

    一般边的容量下限为0，此处将每条边的容量满足l(u,v)<=f(u,v)<=c(u,v)，且l(u,v)>0。求可行流，或者最大流最小流。

 

顶点有容量限制的最大流

    顶点也有容量限制。

 

 /************************************just do it************************************/

 

下面依次对上述问题进行求解。

一. 最大流算法

     最简单的是EK算法，效率不高，我用的加gap优化的SAP，复杂度为(n*n*m)。

 

二. 有上下界的网络流

 

1.无源汇上下界的可行流

    没有源点和汇点，边的容量有上下界up,down。设立源点s和汇点t，计算每个顶点v的入边下界之和减去出边下界之和deg[v]，若deg[v]>0，添加边(s,v,deg[v])；若deg[v]<0，添加边(v,t,-deg[v])，对于原图中的边，上界为up-down。在新图中跑一次最大流，若与s或t相连的边满载，则存在可行流，否则不存在。

 

2.有源汇上下界最大流

    主要思想是二分最大流mid，在无源汇的基础上，连接一条边(t,s,INF-mid,mid)，即在[mid,INF]中二分搜索最大流。（注意枚举下边界时一定要从0开始）。最后若与s‘或者t’相连的边满载，存在最大流，最大流即为的mid。原图每条边的流量为新图的流量+该边的下界。

 

3.有源汇上下界最小流

    做法与有源汇上下界最大流相似，搜索的区间不同，是在[0,mid]中搜索，连接一条边(t,s,mid,0)。同时也要注意枚举的时候从0开始，否则你会很悲剧。。

 

三. 顶点有容量限制的最大流

    在原网络的基础上，将节点u拆成两个点u'和u''，新增加一条弧(u',u'')，容量为u点的限制流量。对于原图中的边(i,j)，变换为(i'',j')，即u点的入边=u'点的入边，出边转移到u''上。

 

 /***********************************just fuck it*************************************/

 

四. 目前学习内容

 

1. 最大流最小割(建模过程)

    具体看胡伯涛的论文，有下面几点技巧：

    a. (不连通)在给定网络流中，去掉割的边集，不存在任何一条由s到t的路径。

    b. (两类点)在给定网络中，任意一个割集将点划分成两部分。割为两部分的“桥梁”。

    c. 用正无限的容量排除不参与决策的边。这样它就不会被选入割集中。

    d. 利用源或汇关联的边容量来处理点权，如最大权闭合图。

    割边的求法：在残余图上从源开始dfs，将图分为两部分，这两部分节点的边集就是割边集。割边都是满流边，但满流边不一定是割边。

 

2. 最大流的0-1规划，参数搜索

    具体参看胡伯涛的论文，它是将最小割与0-1规划结合起来，通过参数搜索来解决问题。如ZOJ2676。

 

3. 最大权闭合图

    一个有向图G的闭合图是该图的一个点集，就是对图中属于闭合图的点u，若存在边(u,v)，则v必属于闭合图中。给每一个点分配一个权值，求最大权闭合图。

    方法：利用最小割模型，设立源点s和汇点t，从s连边到正权值点，容量为该点的权值；对于权值为负的点，连到t，容量为该点的权值的绝对值，原图中的边容量设为正无穷。对新图求最小割，答案=正权值之和-最小割。

    技巧：理解现实生活中的必要条件。若a成立，需要b、c、d作为前提，那么连边(a,b),(a,c),(a,d)。如NOI2006最大获利，HDU3879。

 

4. 有上下界的网络流

    最基础的就是无源汇可行流，然后是有源汇的最大/最小流。如ZOJ2676，SGU176。

    技巧：二分的时候要从0开始，二分结束后，若要输出结果，必须再跑一遍。每条边的流量为：现流量+该边容量的下界。

 

 /************************************keep moving..*******************************/

 

五. 继续学习的内容

1. 混合图的欧拉回路

2. 最小费用最大流

3. 二分图最小点权覆盖和最大点独立集

4. 看论文，了解一些解题技巧，如建模过程中的拆点，拆边。