EK求最大流
// Problem: P3376 【模板】网络最大流
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3376
// Memory Limit: 128 MB
// Time Limit: 2000 ms
// Created Time: 2022-07-05 21:37:49
//
// Powered by CP Editor (https://cpeditor.org)
//fw
#include<bits/stdc++.h>
#define pii pair <int, int>
#define pll pair <ll, ll>
#define endl '\n'
#define il inline
#define pb push_back
#define fi first
#define se second
#define lc u<<1
#define rc u<<1|1
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=2e2+10,M=1e4+10;
int h[N],e[M],ne[M],f[M],idx;//前向星,f表示容量
int n,m,S,T;//点数边数,源点汇点
int q[N],d[N],pre[N];//q:找增广路时宽搜所用队列,d[i]:走到i点时流量的限制,pre记录前驱边,用于更新残留网络
bool st[N];//防止重复搜索
void add(int a,int b,int c)
{
e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;//加入正向边,存储容量
e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;//加反向边,初始流量为0
}
void remake()
{
};
bool bfs()
{
int hh=0,tt=0;//宽搜初始化
memset(st,false,sizeof st);
q[0]=S,st[S]=true,d[S]=INF;//起点没有限制
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];~i;i=ne[i])
{
int ver=e[i];
if(!st[ver]&&f[i])//没有访问过并且流量大于0
{
st[ver]=true;//标记
d[ver]=min(d[t],f[i]);//更新容量限制
pre[ver]=i;//记录前驱边
if(ver==T)return true;//找到增广路则返回
q[++tt]=ver;
}
}
}
return false;
}
ll EK()
{
ll r=0;
while(bfs())//如果存在增广路
{
r+=d[T];//增加流量
for(int i=T;i!=S;i=e[pre[i]^1])//依次更新前驱边的流量
f[pre[i]]-=d[T],f[pre[i]^1]+=d[T];
}
return r;//返回最大流
}
int main()
{
cin>>n>>m>>S>>T;
memset(h,-1,sizeof h);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
cout<<EK()<<endl;
return 0;
}
Dinic求最大流
// Problem: P3376 【模板】网络最大流
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3376
// Memory Limit: 128 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//fw
#include<bits/stdc++.h>
#define zp ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define pii pair <int, int>
#define pll pair <ll, ll>
#define endl '\n'
#define il inline
#define pb push_back
#define fi first
#define se second
#define lc u<<1
#define rc u<<1|1
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=10010,M=200010;
int n,m,S,T;//定义点数、边数、源点、汇点
ll h[N],e[M],ne[M],f[M],idx;//前向星+容量
ll q[N],d[N],cur[N];//宽搜队列、分层图层数、当前弧
void add(int a,int b,int c)
{
e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;//正向边初始容量
e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;//退流管道初始流量为0
}
bool bfs()
{
int hh=0,tt=0;
memset(d,-1,sizeof d);
q[0]=S,d[S]=0;//宽搜以及分层图的初始化
cur[S]=h[S];//记录当前弧初始状态
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];~i;i=ne[i])
{
int ver=e[i];
if(d[ver]==-1&&f[i])//如果没有记录层数并且容量不为0
{
d[ver]=d[t]+1;//记录层数
cur[ver]=h[ver];//初始化节点的当前弧
if(ver==T)return true;//到达汇点则存在增广路
q[++tt]=ver;//将当前点入队
}
}
}
return false;//找不到增广路
}
ll find(int u,int limit)
{
if(u==T)return limit;//到达汇点直接返回流量
ll flow=0;//累加从当前点流出去的可行流
for(int i=cur[u];~i&&flow<limit;i=ne[i])//从当前弧开始遍历
{
cur[u]=i;//当前弧优化,记录已经用到了哪一个点,防止重复搜索已经被榨干的边
ll ver=e[i];
if(d[ver]==d[u]+1&&f[i])//使用分层找到最短的一条增广路,优化搜索顺寻
{
ll t=find(ver,min(f[i],limit-flow));//获得从当前点流出去的可行流,
//下一层的流量值不能超过下一条边的容量和上一层的剩余容量
if(!t)d[ver]=-1;//残枝优化,如果当前点已经没有可行流则把当前点踢出分层图
f[i]-=t,f[i^1]+=t,flow+=t;//正向边可用流量减少,反向边可用流量增加,累加可行流
}
}
return flow;//返回最大可行流
}
ll dinic()
{
ll r = 0, flow;//定义最大可行流r和当前搜索得到的流量flow
while (bfs()) //如果bfs能找到增广路
while (flow = find(S, INF)) //当在这张分层图上仍然能找到可行流时
r += flow;//累加可行流
return r;//返回最大可行流
}
int main()
{
cin>>n>>m>>S>>T;
memset(h,-1,sizeof h);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;//输入正向的点和容量
add(a,b,c);//建立正向边和退流管道
}
cout<<dinic()<<endl;
return 0;
}