中大致谈了一下最大流的一些算法，其中Dinic是非常重要的，补一句：最大流 == 最小割。
本文包括:
1.费用流的概念及基本性质
2.Edmonds-Karp增广路算法求费用流
3.一些关于费用流的技巧
4.关于费用流的刷题指南
1 . 费用流的概念及基本性质
//假设您已经理解了Dinic算法和EK算法二者之一。
对于我们原来的网络流，现在给你一个网络，每条边除了有流量（容量）的限制外，还有一个单位费用，经过这条边，我们不仅要符合可行流的条件，还要付出一个费用 = 单位费用和该边流量之积。 而对于费用流，现在主要可分为“最小费用最大流”和“最大费用最大流”两种基本题型。（至于最小流一般会出现在有上下界的网络流中，这个会在网络流初步详解3中讲解） 最重要的，上述两种基本题型模板基本相同，并且是以最大流为前提。2.Edmonds-Karp增广路算法求费用流
再次重复：您需要理解了Dinic算法和EK算法二者之一，这样你可以在5分钟内学会费用流模板。
我们在这里考虑，为什么不能在Dinic算法的基础上求出费用流。
这里简单谈下，Dinic算法是一个基于残量网络上不断找出増广路的算法，我们在找増广路时，只是考虑了流量和分层图的深度问题，而我们加上单位费用限制后，这种只要可以増广就马上増广的算法就难以变通。 这是我们不妨考虑效率较低，但每次BFS只随机找到一条増广路的Edmonds-Karp增广路算法。我们很容易发现，我们可以限制这个“随机”増广路，从而让它满足费用最大或最小的条件。具体我们将采用一个鲜为人知的被卡死SPFA来实现。先说一下，为了满足我们最大流的“斜对称”原则，及我们可以反悔，以求出最大流，反边的单位费用稍作处理，赋值为 -w
void add_edge(int x, int y, int z, int c) {// 流量限制z，单位费用c to[++tot] = y, w[tot] = z, cost[tot] = c; nex[tot] = head[x], head[x] = tot; to[++tot] = x, w[tot] = 0, cost[tot] = -c;// 这里强调，反边流量初值为0，别无意间打错了 nex[tot] = head[y], head[y] = tot; // 并且费用在回流时要可以返还} 然后我们来讲解具体的最短路上实现増广路操作。(这里给出最小费用最大流)
这里给出2个代码，前者是正确的，而后者可能会出现TLE和WA的错误，请读者仔细思考。AC：bool spfa() { queue q; memset( dis , 0x3f3f3f3f , sizeof(dis) ); memset(v, 0, sizeof(v)); q.push(s); dis[ s ] = 0; v[ s ] = true; //判断是否入队 flow[ s ] = OO ; // 源点无限量 while (q.size()) { int x = q.front(); q.pop(); v[ x ] = false ; for( register int i = head[ x ] ; i ; i = nex[ i ] ){ if (!w[ i ]) continue; // 剪枝 if ( dis[ to[ i ] ] > dis[ x ] + cost[ i ] ){ dis[ to[ i ] ] = dis[ x ] + cost[ i ]; flow[ to[ i ] ] = min( flow[ x ] , w[ i ] ) ; pre[ to[ i ] ] = i; // 记录前驱，更新时使用 if (!v[ to[ i ] ]) v[ to[ i ] ] = true , q.push(to[ i ]) ; } } } if ( dis[t] == 0x3f3f3f3f ) return false; // 汇点不可达，已求出最大流 return true;}void update() { int x = t; while (x != s) { int i = pre[ x ] ; //注意，我们的前缀记录的是边 w[ i ] -= flow[ t ] ; w[ i ^ 1 ] += flow[ t ] ; x = to[i ^ 1] ; } maxflow += flow[ t ] ; ans += dis[ t ]*flow[ t ] ;//这里多解释一下，由于只扫出了一条増广路，不可能存在有像Dinic一样的流量分叉，加之流量守恒定律，所以这条増广路上增加的可行流量在每条边上都相等。} 多种方案可满足最大流时TLE和WA代码片段
for( register int i = head[ x ] ; i ; i = nex[ i ] ){ if (!w[ i ]) continue; // 这一段只放了SPFA更新 int incflow = min( flow[ x ] , w[ i ] ) ; if ( dis[ to[ i ] ] > dis[ x ] + cost[ i ]*incflow ){ dis[ to[ i ] ] = dis[ x ] + cost[ i ]*incflow;//这里是实际消费，而不是单价费用，请读者注意对比！！！ flow[ to[ i ] ] = incflow ; pre[ to[ i ] ] = i; if (!v[ to[ i ] ]) v[ to[ i ] ] = true , q.push(to[ i ]) ; } }}//省略了部分相同代码void update() { int x = t; while (x != s) { int i = pre[ x ] ; w[ i ] -= flow[ t ] ; w[ i ^ 1 ] += flow[ t ] ; x = to[i ^ 1] ; } maxflow += flow[ t ] ; ans += dis[ t ] ;//这里的dis已经是实际消费。} 在感性理解上，2个代码片段给读者的感觉是：好像都一样的呀？而且后者仿佛正确性格更显然啊。在我第一次看的时候，我百思不得其解。为了具体，给你一个样例，请读者不要跳过此节：
假设我现在有 8 的流量要流出，有且仅有两条可行边，都可以满流到达汇点，分别为
A边： 流量为 10 ， 单位费用为 2 。 满流全费 20 B边： 流量为 2 ， 单位费用为 4 。 满流全费 8最优策略（AC代码）：全流A边 20费 。感性策略（WA代码）：B 满流全费小于 A ， B费 8 ， A费16 ， 总费 26 。 感性策略的方法只满足了局部最优解（虽然可以保证最大流），而不能维护整体最优解。 这种情况只有在有多种方案可满足最大流时会中等几率（看数据）TLE或者WA。完整AC代码：（改自李煜东的模板，这个板子亲测常数较小，码风清奇）
#includeusing namespace std;const int MAXN = 5010, MAXM = 100010 , OO = ( 1 << 30 ) ;int to[ MAXM*2 ], w[ MAXM*2 ], cost[ MAXM*2 ], nex[ MAXM*2 ], head[ MAXN ];int dis[ MAXN ] , flow[ MAXN ] , pre[ MAXN ] ;int N , M , s , t , maxflow , ans, tot = 1 ;bool v[ MAXN ] ;inline int read(){ int s = 0,w = 1; char g = getchar(); while(g<'0'||g>'9'){if(g=='-')w*=-1;g = getchar();} while(g>='0'&&g<='9'){s = s*10+g-'0';g = getchar();} return s*w;}//(快读很丑，但费用流代码很好记)void add(int x, int y, int z, int c) { to[++tot] = y, w[tot] = z, cost[tot] = c; nex[tot] = head[x], head[x] = tot; to[++tot] = x, w[tot] = 0, cost[tot] = -c; nex[tot] = head[y], head[y] = tot;}bool spfa() { queue q; memset( dis , 0x3f3f3f3f , sizeof(dis) ); memset(v, 0, sizeof(v)); q.push(s); dis[ s ] = 0; v[ s ] = true; //判断是否入队 flow[ s ] = OO ; // 源点无限量 while (q.size()) { int x = q.front(); q.pop(); v[ x ] = false ; for( register int i = head[ x ] ; i ; i = nex[ i ] ){ if (!w[ i ]) continue; // 剪枝 if ( dis[ to[ i ] ] > dis[ x ] + cost[ i ] ){ dis[ to[ i ] ] = dis[ x ] + cost[ i ]; flow[ to[ i ] ] = min( flow[ x ] , w[ i ] ) ; pre[ to[ i ] ] = i; // 记录前驱，更新时使用 if (!v[ to[ i ] ]) v[ to[ i ] ] = true , q.push(to[ i ]) ; } } } if ( dis[t] == 0x3f3f3f3f ) return false; // 汇点不可达，已求出最大流 return true;}void update() { int x = t; while (x != s) { int i = pre[ x ] ; //注意，我们的前缀记录的是边 w[ i ] -= flow[ t ] ; w[ i ^ 1 ] += flow[ t ] ; x = to[i ^ 1] ; } maxflow += flow[ t ] ; ans += dis[ t ]*flow[ t ] ;}int main() { freopen("minmax.in","r",stdin); N = read() , M = read() , s = read() , t = read() ; for( register int i = 1 ; i <= M ; i++ ){ int m1 = read() , m2 = read() , m3 = read() , m4 = read(); add( m1 , m2 , m3 , m4 ) ; } while (spfa()) update(); // 计算最小费用最大流 cout<< maxflow <<" "<
例题来自洛谷。
3.一些关于费用流的技巧
无论是最大流还是费用流中，读题，抽象，建图，这才是最重要的，板子几乎不会变。
可以在二分图的升级版--带权二分图上愉快地跑网络流。 我们在很多时候都需要拆点操作，以达到限流或限费的目的。 我们在题目中会遇到很多要建立一些 0费的边，以此达到连接和其他的目的。 在【网络流初步详解3】中我还将讲解一些在有上下界的费用流的一些技巧。4.关于费用流的刷题指南
马上上传