$$\color{DarkTurquoise}{知乎网络流学习参考}$$
$$\color{DarkTurquoise}{LibreOJ网络流24题练习}$$
$$\color{DarkTurquoise}{B站网络流学习视频参考}$$
题目描述
如题,给出一个网络图,以及其源点和汇点,求出其网络最大流。
输入格式
第一行包含四个正整数 $n,m,s,t$,分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来 $m$ 行每行包含三个正整数 $u_i,v_i,w_i$,表示第 $i$ 条有向边从 $u_i$ 出发,到达 $v_i$,边权为 $w_i$(即该边最大流量为 $w_i$)。
输出格式
一行,包含一个正整数,即为该网络的最大流。
样例 #1
样例输入 #1
4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 30
样例输出 #1
50
提示
样例输入输出 1 解释
题目中存在 $3$ 条路径:
- $4\to 2\to 3$,该路线可通过 $20$ 的流量。
- $4\to 3$,可通过 $20$ 的流量。
- $4\to 2\to 1\to 3$,可通过 $10$ 的流量(边 $4\to 2$ 之前已经耗费了 $20$ 的流量)。
故流量总计 $20+20+10=50$。输出 $50$。
数据规模与约定
- 对于 $30\%$ 的数据,保证 $n\leq10$,$m\leq25$。
- 对于 $100\%$ 的数据,保证 $1 \leq n\leq200$,$1 \leq m\leq 5000$,$0 \leq w\lt 2^{31}$。
Ford-Fulkerson算法
residual graph
记录网络流中每条流向边的空闲量
,初始化其值为每条边的最大容量
- 每次找一条从起点$s$到终点$t$的
简单路径
(简单路径中的每条边的权值应大于$0$),然后该路径上的每个边减去当前路径能流过的最小流量
$x$,同时添加反向边权值为$x$的边,同时删除权值为$0$的边(其实可以不考虑权值为$0$的边) - 当找不到从起点$s$到终点$t$的
简单路径
,网络流结束. - 该算法的时间复杂度为$O(m\times f)$,其中$m$表示图中
边的数量
,$f$表示最大的网络流
,证明该算法随着网络流
的增大而时间
也是受影响增长 - 比较
暴力
的算法,此代码必然
会在洛谷上超时
// Problem: P3376 【模板】网络最大流
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3376
// Memory Limit: 128 MB
// Time Limit: 2000 ms
// Date: 2023-02-05 16:31:54
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 210
#define MAXM 10010
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,m,s,t;
int head[MAXN],ed[MAXM],nex[MAXM],idx;
ll val[MAXM];
int vis[MAXN];
void add(int a,int b,ll c)
{
ed[idx]=b;
val[idx]=c;
nex[idx]=head[a];
head[a]=idx++;
}
ll dfs(int p,ll flow)
{
if(p==t)//到达终点,返回这条路的流量
return flow;
vis[p]=1;//标记该点走过
for(int i=head[p];i!=-1;i=nex[i])
{
int j=ed[i];
ll c,vol=val[i];
if(val[i]>0&&vis[j]==0&&(c=dfs(j,min(vol,flow)))!=-1)
{
val[i]-=c;//删除该边
val[i^1]+=c;//添加该边
return c;//返回流量
}
}
return -1;//无法到达终点
}
ll Ford_Fulkerson()
{
ll res=0,c;
while((c=dfs(s,inf))!=-1)
{
memset(vis,0,sizeof(vis));
res+=c;
}
return res;
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(0),cout.tie(0);
cin >> n >> m >> s >> t;
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++)
{
int a,b;
ll c;
cin >> a >> b >> c;
add(a,b,c);//建立正向边
add(b,a,0);//建立边权为0的反向边(方便网络流操作)
}
ll res=Ford_Fulkerson();
cout << res << endl;
return 0;
}
Edmond-Karp算法
- 该算法与上一算法的区别在于它是找从起点$s$到终点$t$的
最短路径
作为简单路径
,剩余步骤相同,此处可采用bfs
的方式进行搜索,bfs
可以保证每次找到的都是最短的简单路径
,而dfs
则可能会”绕远路”.
- 该算法的时间复杂度为$O(n\times m^2)$,其中$m$为
边数
,$n$为点数
,与最大流
的大小无关.
// Problem: P3376 【模板】网络最大流
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3376
// Memory Limit: 128 MB
// Time Limit: 2000 ms
// Date: 2023-02-05 16:31:54
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 210
#define MAXM 10010
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,m,s,t;
int head[MAXN],ed[MAXM],nex[MAXM],idx;
ll val[MAXM];
void add(int a,int b,ll c)
{
ed[idx]=b;
val[idx]=c;
nex[idx]=head[a];
head[a]=idx++;
}
int last[MAXN];
ll flow[MAXN];
int bfs()
{
memset(last,-1,sizeof(last));
queue<int> q;
q.push(s);
flow[s]=inf;
while(q.size()>0)
{
int temp=q.front();
q.pop();
if(temp==t)//到达终点
return 1;
for(int i=head[temp];i!=-1;i=nex[i])
{
int j=ed[i];
ll vol=val[i];
if(vol>0&&last[j]==-1)//有空余量且未访问过
{
last[j]=i;//存的是当前的边的编号
flow[j]=min(flow[temp],vol);
q.push(j);
}
}
}
return -1;
}
ll Edmond_Karp()
{
ll maxflow=0;
while(bfs()!=-1)
{
maxflow+=flow[t];
for(int i=t;i!=s;i=ed[last[i]^1])//此处使用的是其反向边,往回走
{
val[last[i]]-=flow[t];
val[last[i]^1]+=flow[t];
}
}
return maxflow;
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(0),cout.tie(0);
cin >> n >> m >> s >> t;
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++)
{
int a,b;
ll c;
cin >> a >> b >> c;
add(a,b,c);//建立正向边
add(b,a,0);//建立边权为0的反向边(方便网络流操作)
}
ll res=Edmond_Karp();
cout << res << endl;
return 0;
}
Dinic算法
- 先用
bfs
构造分层
(预处理出源点到每个点的距离层数
),再用dfs
跑阻塞流
(增广路) - 使用多路增广节省很多花在重复路线上的时间;在某点
dfs
找到一条增广路后,如果还剩下多余的流量未用,继续在该点dfs
尝试找到更多增广路. - 还有当前弧优化,因为在
Dinic算法
中,一条边增广一次后就不会再次增广了,所以下次增广时不需要再考虑这条边.把head数组
复制一份,但不断更新增广的起点.
- 该算法的时间复杂度为$O(n^2 \times m)$,其中$m$为
边数
,$n$为点数
,与最大流
的大小无关
// Problem: P3376 【模板】网络最大流
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3376
// Memory Limit: 128 MB
// Time Limit: 2000 ms
// Date: 2023-02-05 16:31:54
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 210
#define MAXM 10010
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,m,s,t;
int head[MAXN],ed[MAXM],nex[MAXM],idx;
ll val[MAXM];
void add(int a,int b,ll c)
{
ed[idx]=b;
val[idx]=c;
nex[idx]=head[a];
head[a]=idx++;
}
int level[MAXN],now[MAXN];
int bfs()
{
memset(level,-1,sizeof(level));
level[s]=1;
memcpy(now,head,sizeof(now));//当前弧优化初始化
queue<int> q;
q.push(s);
while(q.size()>0)
{
int temp=q.front();
q.pop();
if(temp==t)
return 1;
for(int i=head[temp];i!=-1;i=nex[i])
{
int j=ed[i];
ll vol=val[i];
if(vol>0&&level[j]==-1)
{
level[j]=level[temp]+1;
q.push(j);
}
}
}
return -1;
}
ll dfs(int p,ll flow)
{
if(p==t)
return flow;
ll temp=flow;//剩余的流量
for(int i=now[p];i!=-1&&temp>0;i=nex[i])
{
now[p]=i;//当前弧优化,更新当前弧
int j=ed[i];
ll vol=val[i];
if(vol>0&&level[j]==level[p]+1)//往层数高的方向走
{
ll c=dfs(j,min(vol,temp));//尽可能多的传递流量
temp-=c;//剩余流量减少
val[i]-=c;//更新空闲容量
val[i^1]+=c;//建立反向边,并合并权值
}
}
return flow-temp;//返回变化的流量
}
ll Dinic()
{
ll res=0;
while(bfs()!=-1)
res+=dfs(s,inf);
return res;
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(0),cout.tie(0);
cin >> n >> m >> s >> t;
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++)
{
int a,b;
ll c;
cin >> a >> b >> c;
add(a,b,c);//建立正向边
add(b,a,0);//建立边权为0的反向边(方便网络流操作)
}
ll res=Dinic();
cout << res << endl;
return 0;
}
给出三份代码的运行结果(提交越早,使用的算法越靠前
)
$^{赞}$