Spasmodic @ 2020-08-08 20:55:11
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=205,M=5005,INF=0x3f3f3f3f3f3f3f3f;
ll n,m,s,t,tot=1,hd[N],d[N],ans;
struct edge{ll t,c,nxt;}es[M<<1];
void add(ll u,ll v,ll c){
es[++tot]=(edge){v,c,hd[u]};hd[u]=tot;
es[++tot]=(edge){u,0,hd[v]};hd[v]=tot;
}
bool bfs(){
memset(d,0,sizeof(d));
queue<ll>q;
q.push(s);d[s]=1;
for(ll x;!q.empty();){
x=q.front();q.pop();
for(ll i=hd[x];i;i=es[i].nxt)
if(es[i].c&&!d[es[i].t]){
q.push(es[i].t);
d[es[i].t]=d[x]+1;
if(es[i].t==t)return 1;
}
}
return 0;
}
ll dinic(ll x,ll flow){
if(x==t)return flow;
ll rest=flow,k;
for(ll i=hd[x];i;i=es[i].nxt)
if(es[i].c&&d[es[i].t]==d[x]+1){
k=dinic(es[i].t,min(rest,es[i].c));
es[i].c-=k,es[i^1].c+=k;
rest-=k;
}
if(flow-rest==0)d[x]=-1;
return flow-rest;
}
int main(){
scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
for(ll i=1,u,v,c;i<=m;i++){
scanf("%lld%lld%lld",&u,&v,&c);
add(u,v,c);
}
for(ll flow=0;bfs();)while((flow=dinic(s,INF)))ans+=flow;
printf("%lld",ans);
return 0;
}
by 辰星凌 @ 2020-08-08 20:56:24
Orz网络瘤巨佬
by 辰星凌 @ 2020-08-08 20:57:20
当前狐呢?/yiw
by Earthcomputer @ 2020-08-08 20:57:22
Orz网络瘤巨佬
by optimize_2 @ 2020-08-08 20:58:43
Orz网络瘤巨佬
by WaReTle @ 2020-08-08 20:59:00
当前弧优化?
by Spasmodic @ 2020-08-08 21:00:30
草我大概学了个假的当前弧优化
重学当前弧咯
by Spasmodic @ 2020-08-08 21:07:04
好了 63ms艹了祭
by UltiMadow @ 2020-08-08 21:08:44
@happydef
for(ll i=hd[x];i;i=es[i].nxt)
->
for(ll i=hd[x];i&&rest;i=es[i].nxt)
我之前在这倒过(
by Eason_AC @ 2020-08-08 21:15:56
所以说写EK它不香么(
by Spasmodic @ 2020-08-08 21:19:14
@Eason_AC EK慢