title: '网络流'
date: 2023-01-31 21:31:45
tags: []
published: true
hideInList: false
feature:
isTop: false
定义
给一个有向图 $G=(V,E)$。对于边 $(u,v)$ 有容量 $w(u,v)$。可以理解为为水管在单位时间可以流过的最大水量。现在给定源点 $s$，和汇点 $t$，可以将源点理解为单位时间内可以留任意的水量的水龙头，汇点可以理解为可以装无限水的容器，最大流指源点发出的“水”经过“水管”单位时间可以流到汇点的最大水量。
FF思想
对于求网络最大流问题，我们有一个基础的想法：从源点dfs，如果dfs到了汇点就将这条路径上“流水”，而流的水量就是当前我们dfs到的源点到汇点的路径中边容量的最小值，然后将所有dfs到的边都流去这个水量，相当于将这些边的容量都减少这个水量，在之后的dfs中不走已经满了（没有容量）的边。
但是我们需要改进这个算法，我们发现dfs的一条路径显然不一定是最优的，所以我们让这个算法可以后悔。如何后悔，我们对于每一条边建一条容量为0反向边，每当一条边溜了 $x$ 的流量时就将反向边的容量扩大 $x$ 也就是给自己 $x$ 的反悔空间，那么现在我们就可以写出一个基础代码了，这个基础代码就是FF算法。
tip:对于求一条边的反向边我们可以利用链式前向星存图方式的边的编号，让编号从1开始，这样第 $i$ 条边的反向边的编号就是 $i \bigoplus 1$。
FF
#define inf 1e18+10
long long dfs(int x,long long dis){//dis指流到当前点的流量，返回值是指当前点留到汇点的流量
if(x==t)return dis;//到达汇点
vis[x]=1;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(vis[y]||edge[i].w<=0)continue;//edge[i].w表示当前边的容量，容量没了就留不了
long long tmp=dfs(y,min(dis,edge[i].w));
if(tmp>0){//找到一条路径
edge[i^1].w+=tmp;//留给自己反悔空间
edge[i].w-=tmp;
return tmp;
}
}
}
while(1){//寻找多条路径
fill(vis+1,vis+n+1,false);//记录vis数组是为了避免环
long long res=dfs(s,inf);
if(!res)break;//流不动了就退出
ans+=res;
}cout<<ans;
EK
EK实际上就是把FF算法的dfs换成了bfs，bfs比dfs要快但是无法像dfs一样在回溯的时候修改流量，所以要单独修改边的流量。
flag=true;
while(flag){
flag=false;
fill(vis+1,vis+n+1,false);
queue<int>q;
q.push(s);vis[s]=1;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to
if(!vis[i]&&edge[i].w>0){
vis[i]=1;
q.push(i);
p[x]=i;//记录边
if(i==t){flag=1;break;}//找到路径，退出
}
}
if(flag)break;
}
int pj=inf,x=n;
while(x!=s){//寻找路径中边容量的最小值
pj=min(pj,edge[p[x]].w);
x=edge[p[x]^1].to;
}
x=n;
while(x!=s){//调整边的容量
edge[p[x]].w-=pj;edge[p[x]^1].w+=pj;
x=edge[p[x]^1].to;
}
}
模板 网络最大流
于是我们就可以用上面的算法解决模板题啦~,但毕竟是dfs所以FF只有88分而EK则飞快。
时间复杂度
每寻找一条路径最坏是 $O(n+m)$ 的，而一共最坏会找 $nm$ 次路径，所以复杂度是 $O(nm^2)$ 但是实际上你可以永远相信网络流和数据（跑 $10^5$ 的数据快到飞起）。
Dinic
我们发现dfs有一个很好的特性：对于当前点往后的增广路，如果给进来的流量够的话，可以尽量多找增广路（现在不找以后也会找），这个优化就叫做多路增广。但是这样子的话如果有环的话就会死循环。因此，我们手动让这个图没有环——使用bfs将每个点标深度，然后dfs的时候只允许往比当前深度大 $1$ 的点走。每次增广完后重新确定深度（流满的边不用来确定深度），找新的增广路。
#include<iostream>
#include<queue>
#define inf 10000000000000
using namespace std;
const int maxn=210,maxm=5010;
int n,m,s,t,cnt=1,dep[maxn],head[maxn];
long long ans;
queue<int>q;
struct E{
int to,next;
long long w;
}edge[maxm<<2];
void add(int u,int v,long long w){
edge[++cnt].to=v;edge[cnt].next=head[u];head[u]=cnt;edge[cnt].w=w;
}
bool bfs(){
fill(dep+1,dep+n+1,0);
q.push(s);
dep[s]=1;
bool flag=false;
while(!q.empty()){
int x=q.front();q.pop();
if(x==t)flag=true;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(dep[y]||edge[i].w<=0)continue;
dep[y]=dep[x]+1;//如果可以流的话确定深度
q.push(y);
}
}
return flag;
}
long long dfs(int x,long long flu){//与之前没有大变化
if(x==t)return flu;//找到一条增广路
long long tmp=0;//tmp增广出多少流
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(dep[y]==dep[x]+1&&edge[i].w>0){
int res=dfs(y,min(flu,edge[i].w));
tmp+=res;
flu-=res;//给进来的流减少
edge[i].w-=res;
edge[i^1].w+=res;
if(!flu)break;
}
}
if(!tmp)dep[x]=-114514;//炸点优化——现在无法增广的点在重新确定深度之前仍然无法增广
return tmp;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int u,v;
long long w;
cin>>u>>v>>w;
add(u,v,w);
add(v,u,0);
}
while(bfs()){
ans+=dfs(s,inf);
}
cout<<ans<<endl;
return 0;
}
最小割
最小割：在图中割掉一些边，使得源点和汇点不连通，最小割即这些边权值和的最小值。
定理：最大流=最小割 可以自行查找证明方法
因此可以直接用最大流的代码
刷题
掌握了上面的知识后你就可以看看网络里的题目了。网络流题目在模板写熟练后最难的就是对题目进行建模了。
1.POJ3469
题意
有两个工人，$n$ 个任务，第 $i$ 个任务在第一个工人做的话需要 $a_i$ 的时间，在第二个人做的话要 $b_i$ 的时间，然而有 $m$ 个关系 $(i,j,w)$ 表示第 $i$ 个任务和 $j$ 个任务如果不在同一个工人做的话就需要额外 $w$ 时间，
题解
我们将两个工人看做源点和汇点，然后第一个工人向第 $i$ 个任务建一条权值为 $a_i$ 的边，第 $i$ 个任务向第二个工人建一条权值为 $b_i$ 的边。对于每一个关系 $(i,j,w)$，$i$ 和 $j$ 建一条权值为 $w$ 的双向边，然后求最小割。如果 $i$ 和 $j$ 被不同的工人做了的话，就必须要割掉 $i$到 $j$ 的边来保证源点和汇点不连通。
#include<iostream>
#include<cstring>
#include<queue>
#define inf 100000000000
using namespace std;
const int maxn=500010;
int s,t,n,m,cnt=1,dep[maxn],head[maxn];
long long ans;
queue<int>q;
struct E{
int to,next;
long long w;
}edge[maxn<<2];
void add(int u,int v,long long w){
edge[++cnt].to=v;edge[cnt].next=head[u];head[u]=cnt;edge[cnt].w=w;
}
bool bfs(){
while(!q.empty())q.pop();
fill(dep,dep+n+2,0);
q.push(s);dep[s]=1;
bool flag=false;
while(!q.empty()){
int x=q.front();q.pop();
if(x==t)flag=true;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(dep[y]||edge[i].w<=0)continue;
dep[y]=dep[x]+1;
q.push(y);
}
}
return flag;
}
long long dfs(int x,long long flu){
if(x==t)return flu;
long long tmp=0;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(dep[y]==dep[x]+1&&edge[i].w>0){
int res=dfs(y,min(flu,edge[i].w));
tmp+=res;
flu-=res;
edge[i].w-=res;
edge[i^1].w+=res;
if(!flu)break;
}
}
// if(!tmp)dep[x]=-114514;
return tmp;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
s=0;t=n+1;
for(int i=1;i<=n;i++){
int x,y;cin>>x>>y;
add(s,i,x);
add(i,s,0);
add(i,t,y);
add(t,i,0);
}
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
while(bfs()){
ans+=dfs(s,inf);
}
cout<<ans;
return 0;
}