RT,求大佬指点
#include<bits/stdc++.h>
using namespace std;
const int MAXN=520020;
const int M=2510;
int n,m,s,t,u,v;
long long w,dis[MAXN];
long long head[MAXN],pre[MAXN],vis[MAXN],tot=1;
long long flag[M][M];
long long ans;
struct Edge{
int to,next;
long long val;
}e[MAXN];
void add(int u,int v,long long w){
e[++tot].to=v;
e[tot].val=w;
e[tot].next=head[u];
head[u]=tot;
e[++tot].to=u;
e[tot].val=0;
e[tot].next=head[v];
head[v]=tot;
}
long long bfs(){
for(long long i=1;i<=n;i++)vis[i]=0;
queue<int> q;
//cout<<s<<" ";
q.push(s);
// cout<<q.front()<<" ";
vis[s]=1;
dis[s]=MAXN<<2;
while(!q.empty()){
int x=q.front();
q.pop();
// cout<<1<<" "<<x<<endl;
for(long long i=head[x];i;i=e[i].next){
if(e[i].val==0) continue;
int v=e[i].to;
if(vis[v]==1) continue; //没有访问
vis[v]=1;
dis[v]=min(dis[x],e[i].val);
pre[v]=i; //记录前驱,方便修改
if(v==t) return 1; //找到一条路
q.push(v);
}
}
return 0;
}
void update(){
int x=t;
while(x!=s){
int k=pre[x];
e[k].val-=dis[t];
e[k^1].val+=dis[t];
x=e[k^1].to;
}
ans+=dis[t];
}
int main(){
cin>>n>>m>>s>>t;
for(long long i=1;i<=m;i++){
cin>>u>>v>>w;
if(flag[u][v]==0){
add(u,v,w);
flag[u][v]=tot;
}
else{
e[flag[u][v]-1].val+=w;
}
}
while(bfs()){
update();
}
cout<<ans;
return 0;
}