传送门 Luogu P3376 【模板】网络最大流
题目描述
如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。
输入输出格式
输入格式
第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi）
输出格式
一行，包含一个正整数，即为该网络的最大流。
输入输出样例
输入样例#1
4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40
输出样例#1
50
说明
数据规模
对于30%的数据：N<=10，M<=25
对于70%的数据：N<=200，M<=1000
对于100%的数据：N<=10000，M<=100000
样例说明
题目中存在3条路径：
4-->2-->3，该路线可通过20的流量
4-->3，可通过20的流量
4-->2-->1-->3，可通过10的流量（边4-->2之前已经耗费了20的流量）
故流量总计20+20+10=50。输出50。
算法详解
首先是网络流中的一些定义：
V表示整个图中的所有结点的集合.
E表示整个图中所有边的集合.
G = (V,E) ,表示整个图.
s表示网络的源点,t表示网络的汇点.
对于每条边(u,v),有一个容量c(u,v) (c(u,v)>=0)，如果c(u,v)=0，则表示(u,v)不存在在网络中。相反，如果原网络中不存在边(u,v)，则令c(u,v)=0.
对于每条边(u,v),有一个流量f(u,v).
一个简单的例子.网络可以被想象成一些输水的管道.括号内右边的数字表示管道的容量c,左边的数字表示这条管道的当前流量f.
网络流的三个性质：
1、容量限制: f[u,v]<=c[u,v]
2、反对称性：f[u,v] = - f[v,u]
3、流量平衡: 对于不是源点也不是汇点的任意结点,流入该结点的流量和等于流出该结点的流量和。
只要满足这三个性质,就是一个合法的网络流.
最大流问题，就是求在满足网络流性质的情况下，源点 s 到汇点 t 的最大流量。
求一个网络流的最大流有很多算法 这里首先介绍 增广路算法（EK）
学习算法之前首先看了解这个算法中涉及到的几个图中的定义：
- 残量网络
为了更方便算法的实现，一般根据原网络定义一个残量网络。其中r(u,v)为残量网络的容量。
r(u,v) = c(u,v) – f(u,v)
通俗地讲：就是对于某一条边（也称弧），还能再有多少流量经过。 - 增广路
在残量网络中的一条从s通往t的路径，其中任意一条弧(u,v)，都有r[u,v]>0。 - 增广路算法
每次用DFS找一条最短的增广路径，然后沿着这条路径修改流量值（实际修改的是残量网络的边权）。当没有增广路时，算法停止，此时的流就是最大流。
具体解释看下面的代码注释吧
C++模板代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define rr register
using namespace std;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f;
int n,m,s,t,ans;
int vis[maxn];
struct edge{
int to,c,rev;//边里存储的分别是连接点、容量、反向边的编号
};
vector<edge>a[maxn];
inline int read(){//珂朵莉版快读~~
int chtholly=0,willem=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-')willem=-1;c=getchar();}
while(c<='9' && c>='0'){chtholly=chtholly*10+(int)(c-'0');c=getchar();}
return chtholly*willem;
}
inline void add(int x,int y,int z){
int S1=a[y].size(),S2=a[x].size();
a[x].push_back((edge){y,z,S1});
//对于一条边，它的反向边的编号就是它所连向的点此时所拥有的边的个数+1
//但vector里数组下标都是0开始的，所以直接是a[x].size()就好了
a[y].push_back((edge){x,0,S2});
}
inline int dfs(int x,int y,int now){
if(x==y)return now;
vis[x]=1;
int S=a[x].size();
for(rr int i=0;i<S;++i){
int v=a[x][i].to,f=a[x][i].c,re=a[x][i].rev;
if(!vis[v] && f>0){
int tmp=dfs(v,y,min(f,now));//从子节点开始找增广路
if(tmp>0){//如果存在增广路
a[x][i].c-=tmp;//容量减去增加的流量就相当于流量加上这么多
a[v][re].c+=tmp;//正向边流量增加相当于反向边流量减少
return tmp;
}
}
}
return 0;
}
inline int max_flow(int x,int y){
int flow=0,f=0;
do{
flow+=f;
memset(vis,0,sizeof(vis));
f=dfs(x,y,inf);
//寻找增广路，因为在寻找过程中要取此时的流量与该路径的容量的min值，故流量初始化为极大值
}while(f!=0);//当存在增广路的时候就继续找
return flow;
}
int main(){
n=read(),m=read(),s=read(),t=read();
memset(a,0,sizeof(a));
for(rr int i=1;i<=m;++i){
int x=read(),y=read(),z=read();
add(x,y,z);
}
ans=max_flow(s,t);
printf("%d\n",ans);
return 0;
}
