网络流
最大流
- 暴力求解
第1步：从残存网络中找出一条从起点S到终点T的简单路径。
第2步：基于路径中容量最小的边，更新残留网络
并不能保证找到最大流
- Ford-Fulkerson算法
在暴力的基础上增加了反悔边，保证一定是可以找到最大流的
时间复杂度：O(F*(N + M))
- EK算法
可视为 Ford-Fulkerson算法 用 bfs 实现
初始复制残量网络为原网络
重复以下操作：
- 判断 bfs 能否在残量网络上找到一个从 s 到 t的路径
- 寻找增广路，找出最小剩余容量，更改，增加ans
时间复杂度：O(NM^2)
- dinic 算法
点击查看代码
inline int bfs(){
for(int i=1;i<=cnt;i++) dis[i]=INF;
queue<int>q;
q.push(s);
dis[s]=0;
now[s]=h[s];
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=h[x];i;i=e[i].nex){
int v=e[i].to;
if(e[i].w==0||dis[v]!=INF) continue;
q.push(v);
now[v]=h[v];
dis[v]=dis[x]+1;
if(v==t) return 1;
}
}
return 0;
}
inline ll dfs(int x,ll sum){
if(x==t) return sum;
ll k,res=0;
for(int i=now[x];i&∑i=e[i].nex){
now[x]=i;//当前弧优化
int v=e[i].to;
if(e[i].w>0&&dis[v]==dis[x]+1){
k=dfs(v,min(sum,e[i].w));
if(k==0) dis[v]=INF;//
e[i].w-=k;
e[i^1].w+=k;
res+=k;
sum-=k;
}
}
return res;
}
使用
ll ans=0;
while(bfs()){
ans+=dfs(s,INF);
}
时间复杂度： O(N^2M) 但是实际上跑的很快
在单位容量网络上 时间复杂度大约为 O(m^(3/2))
最小割
最大流==最小割
可以通过从s出发走残量网络找到S点集的点
费用流
SSP 算法
- 贪心思想：每次寻找单位费用最小的增广路进行增广，直到图上不存在增广路为止
单位费用：一条增广路的单位 cst 之和
！ 如果图上存在单位费用为负的圈，SSP 算法无法正确求出该网络的最小费用最大流。此时需要先使用消圈算法消去图上的负圈
点击查看代码
inline int spfa(){
memset(w,0,sizeof(w));
memset(cst,0x7f,sizeof(cst));
queue<int>q;
q.push(s);
w[s]=INF;cst[s]=0;vis[s]=1;
while(!q.empty()){
int u=q.front(); vis[u]=0;q.pop();
for(int i=h[u];i;i=e[i].nex){
int v=e[i].to;
if(e[i].w==0||cst[v]<=cst[u]+e[i].cst) continue;
if(!vis[v]) q.push(v);
vis[v]=1;
pre[v]=i;
cst[v]=cst[u]+e[i].cst;
w[v]=min(w[u],e[i].w);
}
}
return w[t];
}
int flow,cost;
inline void ek(){
while(spfa()){
int u=t;
while(u!=s){
e[pre[u]].w-=w[t];
e[pre[u]^1].w+=w[t];
u=e[pre[u]^1].to;
}
flow+=w[t];
cost+=w[t]*cst[t];
}
}