Mr_ll @ 2021-10-27 17:02:26
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
const int N=10010,M=200010;
int n,m,s,t,u,v;
ll ans,yu[N],cnt=1,w,h[N],dep[N];
struct qwe{
int to,net;
}tr[M];
void add(int x,int y,ll z){
tr[++cnt].to=y;
yu[cnt]=z;
tr[cnt].net=h[x];
h[x]=cnt;
}
bool ff(){
queue<int> q;
memset(dep,0,(n+1)*sizeof(int));
dep[s]=1;
q.push(s);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=h[x];i;i=tr[i].net){
int y=tr[i].to;
if(yu[i]&&!dep[y]){
dep[y]=dep[x]+1;
q.push(y);
}
}
}
return dep[t];
}
ll dfs(int u,ll in){
if(u==t) return in;
ll out=0;
for(int i=h[u];i&∈i=tr[i].net){
int v=tr[i].to;
if(yu[i]&&dep[v]==dep[u]+1){
ll res=dfs(v,min(in,yu[i]));
yu[i]-=res;
yu[i^1]+=res;
in-=res;
out+=res;
}
}
if(out==0) dep[u]=0;
return out;
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++){
scanf("%d%d%lld",&u,&v,&w);
add(u,v,w);
add(v,u,0);
}
while(ff())
ans+=dfs(s,1e18);
printf("%lld\n",ans);
return 0;
}
by Vaino @ 2021-10-27 17:03:00
因为我这个菜鸡坐你旁边导致你变成菜鸡
by Zwaire @ 2021-10-30 06:43:27
@Mr_ll
memset 出了问题,初始化层数是不对的
by Zwaire @ 2021-10-30 06:48:42
@Mr_ll
你上面定义的dep 的类型是ll,8个字节啊
但是下面初始化的时候 int 4个字节肯定会初始化出问题
by Mr_ll @ 2021-10-30 14:28:02
@DRY—AYST 谢谢大佬!