simonG @ 2022-11-14 14:00:49
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N=210,M=5010;
const LL inf=1e18;
int n,m,s,t,u,v;
int tot=1,head[N],ver[M*2],nxt[M*2],flag[N][N];
int pre[N];
LL edge[M*2],minv[N],w,ans;
bool vis[N];
void addedge(int x,int y,LL z) {
ver[++tot]=y;
edge[tot]=z;
nxt[tot]=head[x];
head[x]=tot;
}
bool bfs() {
memset(vis,0,sizeof(vis));
queue<int> q;
q.push(s); vis[s]=1; minv[s]=inf;
for(; q.size(); ) {
int x=q.front(); q.pop();
for(int i=head[x]; i; i=nxt[i]) {
if(edge[i]==0) continue;
int y=ver[i];
if(vis[y]) continue;
minv[y]=min(minv[y],edge[i]);
pre[y]=i; q.push(y); vis[y]=1;
if(y==t) return 1;
}
}
return 0;
}
void update() {
int x=t;
for(; x!=s; ) {
int v=pre[x];
edge[v]-=minv[t];
edge[v^1]+=minv[t];
x=ver[v^1];
}
ans+=minv[t];
}
int main() {
cin>>n>>m>>s>>t;
for(int i=1; i<=m; i++) {
cin>>u>>v>>w;
if(flag[u][v]==0) {
addedge(u,v,w);
flag[u][v]=tot;
addedge(v,u,0);
} else {
edge[flag[u][v]]+=w;
}
}
for(; bfs(); ) {
update();
}
cout<<ans<<endl;
return 0;
}
by zesqwq @ 2022-11-14 14:09:18
minv[y]=min(minv[y],edge[i]);
错了
by zesqwq @ 2022-11-14 14:09:27
@gaosichensb
by CH_mengxiang @ 2022-11-21 22:47:25
head初始化为-1,循环条件由i改为~i