#include <bits/stdc++.h>
using namespace std;
const int N=2e4+5,inf=2e9;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define int long long
namespace flow
{
int head[N],cur[N],ver[N],nxt[N],edge[N],tot=1,gap[N],dep[N];
void add(int x,int y,int z)
{
ver[++tot]=y;
nxt[tot]=head[x];
edge[tot]=z;
head[x]=tot;
}
void adde(int x,int y,int z)
{
add(x,y,z);
add(y,x,0);
}
int n,m,s,t,maxflow;
int dfs(int x,int flow)
{
//cout<<x<<" "<<flow<<endl;
if(x==t) return flow;
int used=0;
for(int &i=cur[x];i;i=nxt[i])
{
int y=ver[i];
//cout<<x<<" "<<y<<endl;
if(edge[i]&&dep[y]==dep[x]-1)
{
int rlow=dfs(y,min(edge[i],flow-used));
edge[i]-=rlow;edge[i^1]+=flow;used+=rlow;
if(used==flow) return used;
}
}
cur[x]=head[x];
if(!--gap[dep[x]]) dep[s]=n+2;
gap[++dep[x]]++;
return used;
}
void doisap()
{
memset(gap,0,sizeof gap);
memset(dep,0,sizeof dep);
gap[0]=n;
for(int i=1;i<=n;i++) cur[i]=head[i];
while(dep[s]<=n) {maxflow+=dfs(s,inf);}
return;
}
}using namespace flow;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)
{
int x,y,z;cin>>x>>y>>z;
adde(x,y,z);
}
doisap();cout<<maxflow<<endl;
//cerr<<"ok\n";
return 0;
}
这份代码实现的最大流算法有误
具体地 dfs函数中的
edge[i^1]+=flow;
应当为
edge[i^1]+=rlow;
这个错误很zz 但是这份代码通过了本题 事实上 它在某OJ的模板题上只能获得分 令人唏嘘
所以数据太淼