网络最大流 Dinic算法
省选爆了qwq
题目描述
给出一个网络图,以及其源点和汇点,求出其网络最大流。
网络流,就像水在一个水渠构成的网络中流一样,源点有无限的水,每条边有最大流量限制,求流到汇点的最大流量。
更菜一点的EK算法自行了解,此处我们用dinic算法解决问题。
这些网络流算法的核心其实都是一样的(HLPP当我没说),就是每次通过bfs找出增广路,然后进行增广。
增广路:即源点到汇点整条路上边权都大于0的点,根据定义,这样的一条路上最小边就是更新的答案。
EK算法之所以低效,是因为它每次用bfs寻找一条增广路,然后进行增广,dinic算法就是通过一整个bfs,将所有可能的路加入分层图,然后用一个dfs进行统一增广,就显得要高效一些。
算法流程
bfs部分:
记录一个\(dep\)函数,记录源点到某个点的距离,对于每条边\((u,v)\),如果\(dep_v\)没有更新过,就将\(dep_v = dep_u + 1\),然后将\(v\)推进队列。这样更新的前提是\(w > 0\),即边权为正的边才考虑走,最后判断一下,如果\(dep_t\)不为inf,则至少有一条增广路可以走,进行dfs
dfs部分:
dfs记录当前到的点x和剩余流量flow,对于x,扫描每一条出边,如果这条出边不在分层图中就不管。扫描到每一个\(v\),记录k为在\(v\)上增广的答案,递归\(v\)时将flow变为\(min(flow,w)\),如果k为0,代表\(v\)已经不能再增广,将\(dep_v\)设为inf。
这时有一个问题:万一增广错了怎么办?我们将\((u,v)\)的剩余流量 -= k,同时将提前建好的反边\((v,u)\)流量 += k,这是给程序一个“反悔”的机会,从反边流回来相当于“撤销”的操作,记当前点x已经增广的流量为res,则每次res += k,当前剩余流量flow -= k即可,如果flow已经等于0,则无法增广,退出递归。
每次需要记录一个vis[x]数组,在开始递归时记为1,结束递归时计为0,为了避免“反复横跳”的情况发生。
Code
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5,M = 5e4 + 5,inf = 0x3f3f3f3f;
struct Edge{
int v,w,next;
}e[M * 2];
int head[N],n,m,s,t,tot = 1,dep[N],dis[N],vis[N],now[N];
inline void add(int x,int y,int z)
{
++tot;
e[tot].v = y;
e[tot].w = z;
e[tot].next = head[x];
head[x] = tot;
++tot;
e[tot].v = x;
e[tot].w = 0;
e[tot].next = head[y];
head[y] = tot;
}
inline bool SPFA()
{
queue <int> q;
memset(dep,0,sizeof(dep));
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
while(!q.empty()) q.pop();
dis[s] = 0;
q.push(s);
now[s] = head[s];
while(!q.empty())
{
int x = q.front();
q.pop();
for(int i = head[x];i;i = e[i].next)
{
int to = e[i].v;
if(e[i].w <= 0) continue;
if(dis[to] == inf)
{
dis[to] = dis[x] + 1;
now[to] = head[to];
q.push(to);
}
}
}
if(dis[t] != inf) return 1;
return 0;
}
inline int dinic(int x,int flow)
{
if(x == t) return flow;
int k,res = 0;
vis[x] = 1;
for(int i = now[x];i && flow;i = e[i].next)
{
now[x] = i;
int to = e[i].v;
if(e[i].w <= 0 || dis[to] != dis[x] + 1 || vis[to]) continue;
k = dinic(to,min(flow,e[i].w));
if(!k) dis[to] = inf;
e[i].w -= k;
e[i ^ 1].w += k;
flow -= k;
res += k;
}
vis[x] = 0;
return res;
}
int main()
{
cin>>n>>m>>s>>t;
int x,y,z;
for(int i = 1;i <= m;i++)
{
cin>>x>>y>>z;
add(x,y,z);
}
long long ans = 0;
while(SPFA())
ans += dinic(s,inf);
cout<<ans;
return 0;
}
最小费用最大流
这个“费用”,就是在每条边的流量之外,加入了一个单位流量费用,现在要求流量最大的同时费用最小。我们发现,一条增广路上的流量是一样的,所以增广路边权之和最小,费用就会最小,所以我们贪心地将bfs改成最短路即可,因为有负权边,所以使用SPFA,在每次记录流量的时候用一个全局变量记录费用
最大费用最大流同理,改为最长路。
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5,M = 5e4 + 5,inf = 0x3f3f3f3f;
struct Edge{
int v,w,c,next;
}e[M * 2];
int head[N],n,m,s,t,tot = 1,dep[N],dis[N],vis[N],now[N];
long long ans2 = 0;
inline void add(int x,int y,int z,int cost)
{
++tot;
e[tot].v = y;
e[tot].w = z;
e[tot].c = cost;
e[tot].next = head[x];
head[x] = tot;
++tot;
e[tot].v = x;
e[tot].w = 0;
e[tot].c = -cost;
e[tot].next = head[y];
head[y] = tot;
}
queue <int> q;
inline bool SPFA()
{
memset(dep,0,sizeof(dep));
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
while(!q.empty()) q.pop();
dis[s] = 0;
q.push(s);
now[s] = head[s];
while(!q.empty())
{
int x = q.front();
q.pop();
vis[x] = 0;
for(int i = head[x];i;i = e[i].next)
{
int to = e[i].v;
if(e[i].w <= 0) continue;
if(dis[to] > dis[x] + e[i].c)
{
dis[to] = dis[x] + e[i].c;
now[to] = head[to];
if(!vis[to])
{
vis[to] = 1;
q.push(to);
}
}
}
}
if(dis[t] != inf) return 1;
return 0;
}
inline int dinic(int x,int flow)
{
if(x == t) return flow;
int k,res = 0;
vis[x] = 1;
for(int i = now[x];i && flow;i = e[i].next)
{
now[x] = i;
int to = e[i].v;
if(e[i].w <= 0 || dis[to] != dis[x] + e[i].c || vis[to]) continue;
k = dinic(to,min(flow,e[i].w));
if(!k) dis[to] = inf;
e[i].w -= k;
e[i ^ 1].w += k;
flow -= k;
res += k;
ans2 += e[i].c * k;
}
vis[x] = 0;
return res;
}
int main()
{
cin>>n>>m>>s>>t;
int x,y,z,cost;
for(int i = 1;i <= m;i++)
{
cin>>x>>y>>z>>cost;
add(x,y,z,cost);
}
long long ans = 0;
while(SPFA())
{
memset(vis,0,sizeof(vis));
ans += dinic(s,inf);
}
cout<<ans<<" "<<ans2;
return 0;
}
标签:head,增广,int,tot,vis,算法,2023.4,Dinic,dis
From: https://www.cnblogs.com/fanghaoyu801212/p/17288817.html