ZR 集训 Day28线性规划与网络流进阶

好文推荐：一些网络流经典建模 - 洛谷专栏 网络流总结 之前初学网络流时并没有在博客上记录，昨天的网络流题也都是用二分图相关算法写的，所以今天先总结一下网络流相关的算法。 前置基础芝士 网络是指一个有向图 $G = (V,E)$，有两个特殊节点：源点 $S$ 和汇点 $T$。每条有向边 $(x,y) \in E$ 都有一个权值 $c(x,y)$，称为边的容量。若 $(x,y) \notin E$，则 $c(x,y) = 0$。 用 $f(x,y)$ 表示边 $(x,y)$ 上的流量，$c(x,y) - f(x,y)$ 称为边的剩余容量。通常用 $f(x,y)/c(x,y)$ 的形式标记边上的流量与容量。 可行流应该满足： 容量限制： $f(x,y) \le c(x,y)$ 流量守恒： $\sum_{(u,x) \in E} f(u,x) = \sum_{(x,v) \in E} f(x,v), \quad x \neq S, x \neq T$。$\sum_{(S,v) \in E} f(S,v)$ 称为整个网络的流量。 最大流：从源点流向汇点的最大流量。 增广路：一条从源点到汇点的所有边的剩余容量 $\ge 0$ 的路径。 残留网：由网络中所有结点和剩余容量大于 0 的边构成的子图，这里的边包括有向边和其反向边。建图时每条有向边 $(x,y)$ 都构建一条反向边 $(y,x)$，初始容量 $c(y,x) = 0$。构建反向边的目的是提供一个“退流管道”，一旦前面的增广路堵死可行流，可以通过“退流管道”退流，提供了“后悔机制”。 网络最大流 EK 算法 一直循环找增广路，如果找到增广路，先把答案加上当前增广路的流量，再将增广路上经过的边全部减去流量，并给反向边加上流量；如果找不到增广路，退出循环，得到答案。 时间复杂度：$O(nm^2)$。 代码： C++#include using namespace std; #define int long long const int N=1e5+10; int h[N],idx=1; struct node{ int v,c,nxt; }e[N*20]; int n,m,s,t; int mf[N],pre[N]; void add(int u,int v,int c){ e[++idx]={v,c,h[u]}; h[u]=idx; } bool bfs(){ memset(mf,0,sizeof mf); queue q; q.push(s); mf[s]=1e9; while(!q.empty()){ int u=q.front(); q.pop(); for(int i=h[u];i;i=e[i].nxt){ int v=e[i].v; if(!mf[v]&&e[i].c){ mf[v]=min(mf[u],e[i].c); pre[v]=i; q.push(v); if(v==t) return 1; } } } return 0; } int ek(){ int ans=0; while(bfs()){ int v=t; while(v!=s){ int ei=pre[v]; e[ei].c-=mf[t]; e[ei^1].c+=mf[t]; v=e[ei^1].v; } ans+=mf[t]; } return ans; } signed main(){ cinnmst; while(m--){ int u,v,c; cinuvc; add(u,v,c); add(v,u,0); } cout#include using namespace std; #define int long long const int N=1e5+10; int h[N],idx=1; struct node{ int v,c,nxt; }e[N*20]; int n,m,s,t; int mf[N],pre[N]; void add(int u,int v,int c){ e[++idx]={v,c,h[u]}; h[u]=idx; } bool bfs(){ memset(mf,0,sizeof mf); queueint q; q.push(s); mf[s]=1e9; while(!q.empty()){ int u=q.front(); q.pop(); for(int i=h[u];i;i=e[i].nxt){ int v=e[i].v; if(!mf[v]&&e[i].c){ mf[v]=min(mf[u],e[i].c); pre[v]=i; q.push(v); if(v==t) return 1; } } } return 0; } int ek(){ int ans=0; while(bfs()){ int v=t; while(v!=s){ int ei=pre[v]; e[ei].c-=mf[t]; e[ei^1].c+=mf[t]; v=e[ei^1].v; } ans+=mf[t]; } return ans; } signed main(){ cinnmst; while(m--){ int u,v,c; cinuvc; add(u,v,c); add(v,u,0); } coutek(); return 0; } Dinic 算法 这里再引入一个概念： 分层图：我们从源点 $S$ 开始 BFS，给每个节点赋予一个层数，表示它距离源点 $S$ 的最短距离。分层的目的是为了使 DFS 时严格按照层数递归，避免走环。 Dinic 算法思想如下： 在残余网络上，用 BFS 从源点 $s$ 到汇点 $t$ 构造分层图； 在当前分层图上，使用 DFS 进行多路增广，在回溯时实时更新剩余容量。 直至在残余网络中，无法从源点 $s$ 到达汇点 $t$。 在 DFS 中，我们有一个当前弧优化，即如果节点 $u$ 的第 $i$ 条邻接边已经达到了容量上限（或者这条边后面的路径已经无法再推送流量了），那么在这一轮 DFS 的后续过程中，节点 $u$ 就不需要再检查第 $i$ 条边及之前的边了。 代码： C++#include using namespace std; #define int long long const int N=1e5+10; int h[N],idx=1; struct node{ int v,c,nxt; }e[N*20]; int n,m,s,t,d[N],cur[N]; void add(int u,int v,int c){ e[++idx]={v,c,h[u]}; h[u]=idx; } bool bfs(){ memset(d,0,sizeof d); queue q; q.push(s); d[s]=1,cur[s]=h[s]; while(!q.empty()){ int u=q.front();q.pop(); for(int i=h[u];i;i=e[i].nxt){ int v=e[i].v; if(!d[v]&&e[i].c){ d[v]=d[u]+1; cur[v]=h[v]; q.push(v); if(v==t) return 1; } } } return 0; } int dfs(int u,int sum){ if(u==t) return sum; int res=0; for(int i=cur[u];i&&resnmst; while(m--){ int u,v,c; cinuvc; add(u,v,c); add(v,u,0); } cout#include using namespace std; #define int long long const int N=1e5+10; int h[N],idx=1; struct node{ int v,c,nxt; }e[N*20]; int n,m,s,t,d[N],cur[N]; void add(int u,int v,int c){ e[++idx]={v,c,h[u]}; h[u]=idx; } bool bfs(){ memset(d,0,sizeof d); queueint q; q.push(s); d[s]=1,cur[s]=h[s]; while(!q.empty()){ int u=q.front();q.pop(); for(int i=h[u];i;i=e[i].nxt){ int v=e[i].v; if(!d[v]&&e[i].c){ d[v]=d[u]+1; cur[v]=h[v]; q.push(v); if(v==t) return 1; } } } return 0; } int dfs(int u,int sum){ if(u==t) return sum; int res=0; for(int i=cur[u];i&&ressum;i=e[i].nxt){ cur[u]=i; int v=e[i].v; if(d[v]==d[u]+1&&e[i].c){ int t=dfs(v,min(e[i].c,sum-res)); if(!t) d[v]=0; e[i].c-=t,e[i^1].c+=t,res+=t; } } return res; } int dinic(){ int ans=0; while(bfs()) ans+=dfs(s,1e18); return ans; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cinnmst; while(m--){ int u,v,c; cinuvc; add(u,v,c); add(v,u,0); } coutdinic(); return 0; } 无源汇上下界可行流 有源汇和无源汇的可行流的最大区别就是有源汇的源点不需要满足流量平衡，而无源汇的由于没有源汇点，所以每一个点都需要满足流量平衡（流量平衡的定义上面有提到）。 我们建两个网络，一个下界网络，一个增量网络。下界网络的流量限制就是原网络的流量下界、增量网络的流量限制就是原网络的流量上界减去流量下界。 例如，对于以下网络： 建出来的下界网络和增量网络就是： 由于这个下界网络是不平衡的，我们考虑在增量网络上跑一个最大流，使得下界网络加上增量网络上跑出来的最大流之后变得平衡了。那这个增量网络怎么修改呢？ 我们举两个例子： 对于点 $2$，它在下界网络上的净流入为 $3$，净流出为 $1$，所以我们希望在增量网络上它的流出流量比流入流量多 $2$，这样加起来就是平衡的了。所以我们在增量网络上新建一个源点 $S$，连一条从 $S$ 到 $2$ 号点的边，流量为 $2$，这样我们在增量网络上跑最大流后，抛去我们刚刚加的边，$2$ 号点的流出流量就肯定比流入流量大 $2$，符合条件。 对于点 $4$，它在下界网络上的净流入为 $,3$，净流出为 $5$，所以我们希望在增量网络上它的流出流量比流入流量少 $2$，所以我们在增量网络上新建一个汇点 $T$，连一条从 $4$ 号点到 $T$ 的边，流量为 $2$，同理的跑完最大流后就符合条件了。 对于每个点，我们都进行这种操作，得到加边后的增量网络如下： 之后对这个增量网络跑最大流。 对于可行流的判定，如果我们加的这些边都跑满了，即最大流等于我们额外添加的从 $S$ 开始的边的容量和（等价于等于额外添加的从流向 $T$ 的边的容量和），说明原网络有可行流。 代码： C++#include using namespace std; #define int long long const int N=1e5+10; int h[N],idx=1,n,m,s,t,d[N],cur[N],in[N],out[N],low[N],eid[N]; struct node{int v,c,nxt;}e[N*25]; void add(int u,int v,int c){ e[++idx]={v,c,h[u]}; h[u]=idx; } bool bfs(){ memset(d,0,sizeof d); queue q;q.push(s);d[s]=1,cur[s]=h[s]; while(!q.empty()){ int u=q.front();q.pop(); for(int i=h[u];i;i=e[i].nxt){ int v=e[i].v; if(!d[v]&&e[i].c){ d[v]=d[u]+1;cur[v]=h[v];q.push(v); if(v==t)return 1; } } } return 0; } int dfs(int u,int sum){ if(u==t)return sum; int res=0; for(int i=cur[u];i&&resnm;s=0,t=n+1; for(int i=1;iuvlr; low[i]=l; add(u,v,r-l);eid[i]=idx; add(v,u,0); out[u]+=l;in[v]+=l; } int ans=0; for(int i=1;iout[i]){ ans+=in[i]-out[i]; add(s,i,in[i]-out[i]);add(i,s,0); } else if(in[i]#include using namespace std; #define int long long const int N=1e5+10; int h[N],idx=1,n,m,s,t,d[N],cur[N],in[N],out[N],low[N],eid[N]; struct node{int v,c,nxt;}e[N*25]; void add(int u,int v,int c){ e[++idx]={v,c,h[u]}; h[u]=idx; } bool bfs(){ memset(d,0,sizeof d); queueint q;q.push(s);d[s]=1,cur[s]=h[s]; while(!q.empty()){ int u=q.front();q.pop(); for(int i=h[u];i;i=e[i].nxt){ int v=e[i].v; if(!d[v]&&e[i].c){ d[v]=d[u]+1;cur[v]=h[v];q.push(v); if(v==t)return 1; } } } return 0; } int dfs(int u,int sum){ if(u==t)return sum; int res=0; for(int i=cur[u];i&&ressum;i=e[i].nxt){ cur[u]=i;int v=e[i].v; if(d[v]==d[u]+1&&e[i].c){ int t_fl=dfs(v,min(e[i].c,sum-res)); if(!t_fl)d[v]=0; e[i].c-=t_fl;e[i^1].c+=t_fl;res+=t_fl; } } return res; } int dinic(){ int flow=0; while(bfs())flow+=dfs(s,1e18); return flow; } signed main(){ ios::sync_with_stdio(0);cin.tie(0); cinnm;s=0,t=n+1; for(int i=1;im;i++){ int u,v,l,r;cinuvlr; low[i]=l; add(u,v,r-l);eid[i]=idx; add(v,u,0); out[u]+=l;in[v]+=l; } int ans=0; for(int i=1;in;i++){ if(in[i]out[i]){ ans+=in[i]-out[i]; add(s,i,in[i]-out[i]);add(i,s,0); } else if(in[i]out[i]){ add(i,t,out[i]-in[i]);add(t,i,0); } } if(dinic()==ans){ cout"Yes\n"; for(int i=1;im;i++) coutlow[i]+e[eid[i]^1].c"\n"; } else cout"No\n"; return 0; } 有源汇上下界可行流 首先我们考虑将有源汇转化为无源汇，不难发现，如下图，当我们从 $T$ 向 $S$ 连一条范围在 $[0,+\infty )$ 的边，这样就能使得源汇点满足流量守恒。 之后，我们借用无源汇上下界可行流的做法，建出下界网络与增量网络（注意区分原图的 $S$，$T$ 与增量网络新建的源汇点 $S'$，$T'$）： 按照无源汇上下界可行流， $S'$，$T'$ 为源汇点跑完最大流后，我们先排除掉不可行的情况。 接下来就是最妙的一步，对于原网络的一个可行流的流量，就应该是下界网络源点所有连出去的边的流量和加上增量网络中源点连出去的边（不包括 $S$ 连向 $T'$）的流量。由于网络是可行流，所以我们加的那些附加边是都跑满的，也就是说 $S$ 连向 $T'$ 的那条边应该是跑满的，它的流量就应该等于下界网络源点所有连出去的边的流量和。所以原网络的可行流流量就可以看作是增量网络中源点连出去的边（包括 $S$ 连向 $T'$）的流量。由于流量守恒可知，它恰恰等于增量网络中 $T$ 流向 $S$ 的流量，因为只有这一条边连向 $S$。所以我们就找到了可行流。 有源汇上下界最大流 找到可行流后，我们紧接着很快就能找到最大流。 我们考虑在增量网络的残余网络上删除 $T$ 流向 $S$ 的这条边，之后以 $S$，$T$ 为源汇点再跑一遍最大流，得到的结果与先前算出来的可行流相加，就是原网络的最大流。 为什么是对的？ 首先，原本的可行流保证了流量守恒，而对于我们添加的那些附加边，在可行的条件下是一定跑满了的，所以从 $S$，$T$ 是走不到 $S'$，$T'$ 的。 代码： C++#include using namespace std; #define int long long const int N=1e5+10,INF=1e18; int idx=1,n,m,s,t; int h[N],d[N],cur[N],in[N],out[N]; struct node{int v,c,nxt;} e[N*30]; void add(int u,int v,int c){ e[++idx]={v,c,h[u]}; h[u]=idx; } bool bfs(){ memset(d,0,sizeof d); queue q; q.push(s); d[s]=1,cur[s]=h[s]; while(!q.empty()){ int u=q.front();q.pop(); for(int i=h[u];i;i=e[i].nxt){ int v=e[i].v; if(!d[v]&&e[i].c){ d[v]=d[u]+1,cur[v]=h[v]; q.push…