网络流学习笔记
概念
最大流: 在一个网络图上，每个边有流量限制，假如起始点有无线流量，求最多能有多少流量流到终点。
增广路: 一条从起始点到终点了路径，可以流流量。
算法
Ford-Fulkerson算法
解决这个问题，可以用Ford-Fulkerson算法。
该算法的核心就是寻找增广路。每找到一条增广路，就给它它能承受的最多流量。
我们注意到这样是有问题的，很可能最终结果不是最优的。因为先找到的增广路可能导致超过一条增广路断掉，最终答案劣。所以考虑反悔贪心。
反悔操作可以用反向边完成。建立反向边，每次增广路把正向边的流量给到反向边。这样一旦选到反向边，就相当于撤销了一次对边的选择操作，并把两次操作合并。可以证明这是最优的。
dfs爆搜即可。
Dinic算法
Dinic是针对FF的一种优化。
先使用bfs为所有点分层，然后每次dfs爆搜，只需要走层数较高的点，避免搜重和环。
弧优化
基于链式前向星，剪掉无用的dfs过程。分层后因为向回搜索不优，剪掉。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#define int long long
#define TOP st
using namespace std;
int tot=1,head[100004],n,m,st,ed,now[100004],tppo;
struct node
{
int to,nex,w;
}e[100004],E[100004];
int ds[100004],nw[100004];
void add(int u,int v,int w)
{
// cout<<u<<" "<<v<<' '<<w<<endl;
e[++tot].to=v;
e[tot].w=w;
e[tot].nex=head[u];
head[u]=tot;
e[++tot].to=u;
e[tot].w=0;
e[tot].nex=head[v];
head[v]=tot;
}
bool bfs()
{
for(int i=1;i<=TOP;i++)
{
ds[i]=10000000000;
}
queue<int> q;
q.push(st);
ds[st]=0;
now[st]=head[st];
bool ret=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=E[i].nex)
{
int v=E[i].to;
if(E[i].w>0&&ds[v]==10000000000)
{
q.push(v);
now[v]=head[v];
ds[v]=ds[u]+1;
}
}
}
return ds[ed]!=10000000000;
}
int dfs(int u,int sum)
{
if(u==ed) return sum;
int re=0,las;
for(int i=now[u];i&∑i=E[i].nex)
{
now[u]=i;
int v=E[i].to;
if(E[i].w>0&&ds[v]==ds[u]+1)
{
las=dfs(v,min(sum,E[i].w));
if(las==0) ds[v]=10000000000;
E[i].w-=las;
E[i^1].w+=las;
re+=las;
sum-=las;
}
}
return re;
}
int Gans()
{
memcpy(E,e,sizeof(e));
memset(now,0,sizeof(now));
memset(ds,0,sizeof(ds));
int ans=0;
while(bfs())
{
ans+=dfs(st,10000000000);
}
return ans;
}
signed main()
{
int ans=0;
scanf("%lld%lld%lld%lld",&n,&m,&st,&ed);
for(int i=1,u,v,w;i<=m;i++)
{
scanf("%lld%lld%lld",&u,&v,&w);
add(u,v,w);
}
cout<<Gans();
}最小割
两点之间的割表示删除一些边使得两点不联通，这些边的边权和。
最小割指最小的割。
有结论：最大流=最小割
首先，割掉所有满流的边。若没有增广路，则此时两点必不联通，而流量恰巧就是所有流满边的边权之和，否则一定存在更大流。
一般用途在多个条件选一个条件满足，每个条件有代价的题目里面。
找到一组最小割，你需要从源点 dfs 只走非
费用流
每个边流流量要费用，求在最大流的情况下最小费用。
由于增广顺序不影响，所以每次寻找最小费用增广路即可。
把 bfs 改成 SPFA（有负权边）搜索分层即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#define int long long
using namespace std;
int tot=1,head[1000004],n,m,st,ed,now[1000004],tppo;
struct node
{
int to,nex,w,co;
}e[1000004],E[1000004];
int ds[1000004],nx[1000004],wnx[1000004];
bool inq[1000004];
void add(int u,int v,int w,int co)
{
// cout<<u<<" "<<v<<' '<<w<<endl;
e[++tot].to=v;
e[tot].w=w;
e[tot].co=co;
e[tot].nex=head[u];
head[u]=tot;
e[++tot].to=u;
e[tot].w=0;
e[tot].nex=head[v];
head[v]=tot;
e[tot].co=-co;
}
bool bfs()
{
int las=ds[ed];
for(int i=0;i<=n;i++)
{
ds[i]=1000000000000000;
inq[i]=false;
wnx[i]=0;
nx[i]=0;
}
queue<int> q;
q.push(st);
ds[st]=0;
inq[st]=true;
while(!q.empty())
{
int u=q.front();
q.pop();
inq[u]=false;
for(int i=head[u];i;i=E[i].nex)
{
int v=E[i].to;
if(E[i].w>0&&ds[v]>ds[u]+E[i].co)
{
if(!inq[v])
{
inq[v]=true;
q.push(v);
}
nx[v]=u;
wnx[v]=i;
ds[v]=ds[u]+E[i].co;
}
}
}
return ds[ed]!=1000000000000000;
}
pair<int,int> Gans()
{
memcpy(E,e,sizeof(e));
memset(now,0,sizeof(now));
memset(ds,0,sizeof(ds));
int ans=0,rans=0;
while(bfs())
{
int nw=ed,ll=1000000000000000;
while(nw!=st)
{
ll=min(ll,E[wnx[nw]].w);
nw=nx[nw];
}
nw=ed;
while(nw!=st)
{
E[wnx[nw]].w-=ll;
E[wnx[nw]^1].w+=ll;
rans+=E[wnx[nw]].co*ll;
nw=E[wnx[nw]^1].to;
}
ans+=ll;
}
return make_pair(ans,rans);
}
signed main()
{
int ans=0;
scanf("%lld%lld%lld%lld",&n,&m,&st,&ed);
for(int i=1,u,v,w,co;i<=m;i++)
{
scanf("%lld%lld%lld%lld",&u,&v,&w,&co);
add(u,v,w,co);
}
pair <int,int> kans=Gans();
cout<<kans.first<<' '<<kans.second;
}上下界网络流
无源汇可行流
判断是否有可行流使得满足流量上下界且平衡。
首先每个点先流下界。此时网络不平衡。
给一些边增加流量。新建一个网络流。
此时每个边可以增加的流量是上界减下界，所以每条边边权设为上界减下界。新增源点汇点。然后如果一条边需要流量，那么他向源点需要的流量，否则多余流量，向汇点连多余的流量。
对这个网络流跑最大流。判断是否所有点都平衡了，这相当于所有连向源点汇点的边满流。此时每个边的流量就是下界加当前对应边的流量。不满足就没有。
有源汇可行流
多了源点汇点，其实可以在源点汇点之间建立下界
有源汇最大流
首先解决可行流。
然后每条边减去可行流，相当于没有下界。
直接跑最大流再加起来即可。
相当于跑完残余流量。
有源汇最小流
首先解决可行流。
然后每条边变成可行流和下界的差。
直接跑最大流再减掉即可。
相当于去除多余流量。