zhoukangyang @ 2020-05-30 09:42:05
#include<bits/stdc++.h>
#define inf (1<<30)
#define N 11010
#define M 120010
using namespace std;
int n,m,s,t,sum,cc[N],use[N],yflow[N],flag[N],cntcc[N];
struct cmp {
bool operator()(int a,int b) const {
return cc[a]<cc[b];
}
};
priority_queue<int,vector<int>,cmp> q;
struct node {
int to,next,val;
} e[M<<1];
int head[N],last[N];
void add(int x,int y,int val,int id) {
if(head[x]==0) head[x]=id;
else e[last[x]].next=id;
last[x]=id,e[id].val=val,e[id].to=y;
}
void bfs() {
for(int i = 1; i <= n; i++) cc[i] = inf;
use[1]=t,cc[t]=0;
int u=0,v=1;
while(u<v) {
++u;
int fst=use[u];
for(int i = head[fst]; i != 0; i = e[i].next) {
if(cc[e[i].to]!=inf) continue;
if(e[i^1].val==0) continue;
++v,cc[e[i].to]=cc[fst]+1,use[v]=e[i].to;
}
}
use[s]=n;
}
void HLPP() {
bfs();
if(cc[s]==inf) return;
cc[s]=n;
for(int i = 1; i <= n; i++) if(cc[i] != inf) cntcc[cc[i]]++;
for(int i = head[s]; i != 0; i = e[i].next) {
yflow[e[i].to] = e[i].val , e[i^1].val += e[i].val , e[i].val = 0;
if(e[i].to!=s&&e[i].to!=t&&flag[e[i].to]==0) flag[e[i].to]=1,q.push(e[i].to);
}
while(!q.empty()) {
int now = q.top();
q.pop();
flag[now]=0;
if(cc[now]==n+1) continue;
for(int i = head[now]; i != 0; i = e[i].next) if(cc[now]==cc[e[i].to]+1) {
int flow=min(yflow[now],e[i].val);
if(flow == 0) continue;
e[i].val-=flow,e[i^1].val+=flow;
yflow[now]-=flow,yflow[e[i].to]+=flow;
if(e[i].to!=s&&e[i].to!=t&&flag[e[i].to]==0) flag[e[i].to]=1,q.push(e[i].to);
}
if(yflow[now]) {
--cntcc[cc[now]];
if(cntcc[cc[now]]==0) for(int i = 1; i <= n; i++) if(cc[i]>cc[now]&&i!=s&&i!=t&&cc[now]<=now) cc[now]=n+1;
cc[now]=n+1;
for(int i = head[now]; i != 0; i = e[i].next) if(e[i].val) cc[now]=min(cc[e[i].to]+1,cc[now]);
++cntcc[cc[now]];
flag[now]=1,q.push(now);
}
}
}
signed main() {
int x,y,z;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i = 1; i <= m; i++) {
scanf("%d%d%d",&x,&y,&z);
add(x,y,z,i*2);
add(y,x,0,i*2+1);
}
HLPP();
printf("%d\n",yflow[t]);
return 0;
}
HLPP求助,禁止无意义评论