【学习笔记】网络流

背景

马上ICPC了，很惊奇的发现自己没整理网络流的板子。

最大流 dinic

这里选用的是二分图最大匹配的板子：飞行员配对方案问题

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,inf=1e18;
struct E
{int to,next,lim;E(){to=next=lim=0;}E(int x,int y,int z):to(x),next(y),lim(z){}
};
vector<E> e;
vector<int> d,ls,cur;
int m,n;
void add(int u,int v,int lim)
{e.push_back(E(v,ls[u],lim));ls[u]=e.size()-1;
}
bool bfs(int S,int T)
{d.assign(n+3,0);d[S]=1;queue<int> q;q.push(S);while(!q.empty()){int u=q.front(); q.pop();for(int i=ls[u]; i; i=e[i].next){int v=e[i].to;if(d[v]>0||e[i].lim==0) continue;d[v]=d[u]+1;if(v==T) return 1;q.push(v);}}return 0;
}
int dfs(int u,int flow)
{if(u==n+2||flow==0) return flow;int res=0;for(int &i=cur[u]; i; i=e[i].next){int v=e[i].to;if(d[u]+1!=d[v]||e[i].lim==0) continue;int f=dfs(v,min(flow-res,e[i].lim));e[i].lim-=f;e[i^1].lim+=f;res+=f;if(flow==res) break;}return res;
}
int dinic(int S,int T)
{int res=0;while(bfs(S,T)){cur=ls;int p=dfs(S,inf);res+=p;}return res;
}
void O_o()
{cin>>m>>n;int S=n+1,T=n+2;
//	vector E(n+3,vector<array<int,2>>());e.push_back(E());e.push_back(E());ls.assign(n+3,0);while(1){int x,y;cin>>x>>y;if(x>y) swap(x,y);if(x==-1&&y==-1) break;add(x,y,1);add(y,x,0);}for(int i=1; i<=m; i++){add(S,i,1);add(i,S,0);}for(int i=m+1; i<=n; i++){add(i,T,1);add(T,i,0);}cout<<dinic(S,T)<<"\n";for(int u=m+1; u<=n; u++){for(int i=ls[u]; i; i=e[i].next){int v=e[i].to;if(v<=n&&e[i].lim>0){cout<<v<<" "<<u<<"\n";}}}
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cout<<fixed<<setprecision(12);int T=1;
//	cin>>T;while(T--){O_o();}
}

费用流

选用的题目：[NOI2008] 志愿者招募
建边规则：
$u->v:f=flow,w=cost$
$v->u:f=0,w=-cost$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,inf=1e18;
struct E
{int to,next,lim,cost;E(){to=next=lim=cost=0;}E(int a,int b,int c,int d):to(a),next(b),lim(c),cost(d){}
};
vector<E> e(2);
vector<int> ls,dis;
vector<bool> vis;
void add(int u,int v,int c,int w)
{e.push_back(E(v,ls[u],c,w)); ls[u]=e.size()-1;e.push_back(E(u,ls[v],0,-w)); ls[v]=e.size()-1;
}
int n,m,S,T,ans=0;
bool spfa()
{vis.assign(n+4,0);dis.assign(n+4,inf);queue<int> q;q.push(S);vis[S]=1;dis[S]=0;while(!q.empty()){int u=q.front(); q.pop();vis[u]=0;for(int i=ls[u]; i; i=e[i].next){int v=e[i].to;if(e[i].lim==0||dis[v]<=e[i].cost+dis[u]) continue;dis[v]=e[i].cost+dis[u];if(!vis[v]){vis[v]=1;q.push(v);}}}return dis[T]<inf/2;
}
int dfs(int u,int flow)
{vis[u]=1;if(u==T){return flow;}int res=0;for(int i=ls[u]; i; i=e[i].next){int v=e[i].to;if(dis[v]!=dis[u]+e[i].cost||e[i].lim==0||vis[v]) continue;auto p=dfs(v,min(flow,e[i].lim));if(p){e[i].lim-=p;e[i^1].lim+=p;res+=p;ans+=p*e[i].cost;flow-=p;if(!flow) return res;}}return res;
}
int costflow()
{int res=0;while(spfa()){vis[T]=1;while(vis[T]){vis.assign(n+4,0);res+=dfs(S,inf);}}return res;
}void O_o()
{cin>>n>>m;S=n+2; T=n+3;ls.assign(n+4,0);	for(int i=1; i<=n; i++){int x;cin>>x;add(i,i+1,inf-x,0);}add(S,1,inf,0);add(n+1,T,inf,0);for(int i=1; i<=m; i++){int l,r,v;cin>>l>>r>>v;r++;add(l,r,inf,v);}costflow();cout<<ans<<"\n";
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cout<<fixed<<setprecision(12);int T=1;
//	cin>>T;while(T--){O_o();}
}

无源汇可行流

本部分参考：https://zhuanlan.zhihu.com/p/324507636

定义：
下界网络：边流量为 $l$ 组成的网络。
差网络：边流量为 $r-l$ 组成的网络。

建图过程

1. 把差网络的边加入图中，称为非附加边
2. 建立超级源 $SS$，超级汇 $TT$
3. 记 $d_u$ 为下界网络中流入的流量 - 流出的流量。
4. 如果 $d_u>0$，那么我们从 $SS$ 向 $u$ 连一条流量为 $d_u$ 的边，称为附加边。这样在最终的网络中，去掉附加边后，流出的流量会比流入的多 $d_u$，平衡了下界网络。
5. 同理，如果 $d_u<0$，那么我们从 $u$ 向 $TT$ 连一条流量为 $-d_u$ 的边，称为附加边。
6. 所有的附加边费用都应该为0

如果跑一遍最大流，附加边的流量没跑满，那么这张图就不存在可行流。
把所有边的流量加上 $l$ 就是一个可行流。

有源汇可行流

在无源汇图的基础上，从 $T$ 向 $S$ 连一条流量上限为 $inf$，费用为 $0$ 的附加边。注意这是原图的源点和汇点，不是附加的。这样就把问题转换为了无源汇的可行流问题（因为流量平衡了）。可行流的大小等于新加的这条边的流量大小。

有源汇上下界最大流

把图中所有的附加边删掉，根据残余网络从 $S$ 到 $T$ 跑一遍最大流。这相当于把流量给榨干。再加上可行流就是最大流。

但其实除了 $T$ 到 $S$ 的那条附加边，其他的边是不用删的，因为他们已经流满了，并且 $SS$ 和 $TT$ 的 入度/出度为0，不会对答案产生影响。

有源汇上下界最小流

和最大流类似，从 $T$ 到 $S$ 跑一遍最大流，用可行流减去最大流即可。这相当于是把不必要的流量还回去。