Yuzilihhh @ 2024-05-19 21:04:57
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define lf long double
#define INF 0x7fffffffffff
#define debug(alpha) cout<<alpha<<endl
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)
#define Max3(a,b,c) (max(max((a),(b)),(c)))
#define Min3(a,b,c) (min(min((a),(b)),(c)))
using namespace std;
namespace io
{
template<typename T> inline void iread(T &x114){
char c=' ';int wx114=1;x114=0;
while(!isdigit(c)){c=getchar();if(c=='-')wx114=-1;}
while(isdigit(c)){x114=x114*10+c-'0';c=getchar();}
x114*=wx114;
}
template<typename T> inline void write(T x114){
if(x114==0){putchar('0');return;}
if(x114<0){putchar('-');x114=-x114;}
int stk[50],top=0;
while(x114){stk[++top]=x114%10;x114/=10;}
while(top) putchar(stk[top--]+'0');
}
}
/*
Dinic算法与EK算法相同
都是通过累加增广路
带给汇点的流量计算最大流
Dinic算法的卓越性在于同时寻找多条增广路
*/
const int N=1005;
struct edge
{
int v,w,nxt;
}e[200005];
int idx;// 存边
int n,m,s,t;
int h[N],cur[N],d[N];// 链式前向星存储边 当前弧优化 该点层级
void add(int u,int v,int w)// 加边
{
e[++idx]={v,w,h[u]};
h[u]=idx;
}
bool bfs()// 每次进行搜索前先给点分层
{
memset(d,0,sizeof d);
queue<int> q;
q.push(s);
d[s]=1;
// bfs暴力分层,不说了
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(d[v]==0&&e[i].w)
{
d[v]=d[u]+1;
q.push(v);
if(v==t) return true;// 还能到汇点,返回true
}
}
}
return false;// 到不了,返回false
}
int dfs(int u,int mf)
{
if(u==t) return mf;
int sum=0;// 累加流量需求
for(int i=cur[u];i;i=e[i].nxt)
{
cur[u]=i;// 当前弧优化
/*
当前弧优化需要结合后面的余量优化来理解
余量优化会提前退出查找
但是我这一条增广路还没有流满
下次我再回来的时候(重边)
我再补上这条边剩下应得的流量
*/
int v=e[i].v;
if(d[v]==d[u]+1&&e[i].w)// 注意这里有层级限制,只能流向下一层的点
{
int f=dfs(v,min(mf,e[i].w));// 查找以x点出发的多条增广路所需流量和
e[i].w-=f;
e[i^1].w+=f;// 更新残留网
sum+=f;// 累加x点对汇点的贡献
mf-=f;// 从我剩余的流量里扣除本次流量
if(mf==0) // 如果没有流量了(余量优化)
break;// 直接跳出,没有多余流量找增广路了
}
}
if(sum==0)// 如果我怎么走也无法对答案产生贡献(残枝优化)
d[u]=0;// 下次不要来了,来了也没贡献
return sum;
}
int Dinic()
{
int ft=0;
while(bfs())// 对点分层
{
memcpy(cur,h,sizeof h);// 新的一轮,从头开始
ft+=dfs(s,INF);
}
return ft;
}
int u,v,w;
signed main()
{
cin>>n>>m>>s>>t;
for(int i=1;i<=m;++i)
{
io::iread(u);
io::iread(v);
io::iread(w);
add(u,v,w);
add(v,u,0);
}
cout<<Dinic();
return 0;
}
目前看来应该没什么问题,注释写的很清晰,麻烦看一下
by silent_ST @ 2024-05-19 21:12:07
idx 的初始值 为 1。
by Yuzilihhh @ 2024-05-20 21:58:35
@silent_ST 谢谢,我是SB