pengze36 @ 2024-12-07 10:17:24
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
int n,m,s,t;
bool vis[2100];
int head[2100],ver[100005],nnext[100005];
int c[100005];
int tot;
inline void add(int x,int y,ll cx){
ver[++tot]=y;
nnext[tot]=head[x];
head[x]=tot;
c[tot]=cx;
}
inline int dfs(int u,int minf){
if(u==t||minf==0) return minf;
vis[u]=1;
for(int i=head[u];i;i=nnext[i]){
int v=ver[i];
if(c[i]&&(!vis[v])){
int f=dfs(v,min(minf,c[i]));
if(f>0){
c[i]-=f;
if(i&1) c[i+1]+=f;
else c[i-1]+=f;
return f;
}
}
}
return 0;
}
inline ll FF(){
ll maxflow=0;
while(1){
memset(vis,0,sizeof vis);
ll f=dfs(s,0x3f3f3f3f3f3f3f3f);
if(f==0) break;
maxflow+=(ll)f;
}
return maxflow;
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for( int i=1;i<=m;++i){
int u,v;
int w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,0);
}
printf("%lld\n",FF());
return 0;
}
by yanmingqian @ 2024-12-07 10:19:30
@pengze36 FF时间复杂度无法通过此题