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 Eason_AC @ 2020-08-08 21:22:06
@happydef 好吧确实dinic跑起来比EK快qwq
by xiaoyaowudi @ 2020-08-09 08:05:30
orz网络瘤巨佬
by xiaoyaowudi @ 2020-08-09 08:14:25
专题模拟赛的前一天晚上你还在调模板珂海星
by Real_Create @ 2020-08-10 16:17:35
hpdftxdy!