zzxLLL @ 2021-11-20 17:51:50
记录详情: https://www.luogu.com.cn/record/63156415
代码:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M=5010;
struct node{
int to,next,dis;
}edge[M<<1];
int head[M],cnte;
void add(int u,int v,int w){
edge[++cnte].to=v;
edge[cnte].dis=w;
edge[cnte].next=head[u];
head[u]=cnte;
}
int n,m,s,t,ans;
int dis[M];
bool bfs(){
for(int i=0;i<M;i++) dis[i]=0;
dis[s]=1;
queue<int>q;
q.push(s);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].to;
if(!dis[v]&&edge[i].dis>0) dis[v]=dis[u]+1,q.push(v);
}
}
return dis[t];
}
int dfs(int u,int in){
if(u==t) return in;
int out=0;
for(int i=head[u];~i&&in>0;i=edge[i].next){
int v=edge[i].to;
if(edge[i].dis>0&&dis[v]==dis[u]+1){
int res=dfs(v,min(edge[i].dis,in));
edge[i].dis-=res;
edge[i^1].dis+=res;
in-=res,out+=res;
}
}
if(out==0) dis[u]=-100000;
return out;
}
signed main(){
for(int i=0;i<M;i++) head[i]=-1;
scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
for(int i=1,u,v,w;i<=m;i++){
scanf("%lld%lld%lld",&u,&v,&w);
add(u,v,w),add(v,u,0);
}
while(bfs()) ans+=dfs(s,1e18);
printf("%lld",ans);
return 0;
}
by zzxLLL @ 2021-11-20 22:05:52
A了
加边时cnt要初始化为1
int head[M],cnte=1;