YONIC @ 2022-05-21 08:33:07
建图时tot设0会WA#11,但是#9#10AC,设1会TLE#9#10,但#11AC
#include<bits/stdc++.h>
#define int long long
#define M 203
#define M2 (int)(5e3+3)
using namespace std;
int n,m,s,t,now,ans,dep[M<<1],l,r;
queue<int>Q;
bool vis[M];
class graph{
public:
int tot=1,head[M<<1];
class edge{
public:
int nxt,to,w;
};
edge h[M2<<1];
void add(int u,int v,int w){
h[++tot].to=v;
h[tot].nxt=head[u];
h[tot].w=w;
head[u]=tot;
}
};
graph G;
bool BFS(){
memset(dep,0,sizeof(dep));
Q.push(s);
dep[s]=1;
while(!Q.empty()){
int x=Q.front();
Q.pop();
for(int i=G.head[x];i;i=G.h[i].nxt){
int y=G.h[i].to;
if(G.h[i].w&&!dep[y]){
dep[y]=dep[x]+1;
Q.push(y);
}
}
}
return dep[t];
}
int DFS(int x,int in){
if(x==t) return in;
int out=in;
for(int i=G.head[x];i&&out;i=G.h[i].nxt){
int y=G.h[i].to;
if(G.h[i].w&&dep[y]==dep[x]+1) {
int res=DFS(y,min(G.h[i].w,out));
G.h[i].w-=res;
G.h[i^1].w+=res;
out-=res;
if(!out) break;
}
}
if(!out) dep[x]=0;
return in-out;
}
signed main(){
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);
G.add(u,v,w);
G.add(v,u,0);
}
while(BFS()) ans+=DFS(s,1e18);
printf("%lld\n",ans);
return 0;
}
by LCATreap @ 2022-05-21 12:40:54
把 if(!out)dep[x]=0;
改成 if(out == in)dep[x]=0;
关我大号就行(
by LCATreap @ 2022-05-21 12:43:31
至于为什么 tot=0
会炸是因为反向边对应不上,tot=1
没问题。