幻离ian @ 2021-07-08 17:23:51
#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>
#define int long long
using namespace std;
int INF=1ll<<62;
int n,m,s,t,res,tot,pre[205],vis[205],u,v,c;
int f[205][205];
inline int bfs(){
memset(vis,0,sizeof(vis));
pre[t]=0;
queue<int>q;
q.push(s);
vis[s]=1;
int lf=INF;
while(!q.empty()){
int x = q.front();q.pop();
if(x==t)break;
for(int i = 1;i<=n;i++){
if(vis[i]==0&&f[x][i]>0){
q.push(i);
lf=min(lf,f[x][i]);
pre[i]=x;
vis[i]=1;
}
}
}
if(pre[t]==0)return 0;
return lf;
}
inline void upt(int flow){
int x=t;
while(x!=s){
f[pre[x]][x]-=flow;
f[x][pre[x]]+=flow;
x=pre[x];
}
}
signed main(){
cin>>n>>m>>s>>t;
for(int i = 1;i<=m;i++){
cin>>u>>v>>c;
f[u][v]+=c;
}
while(1){
res=bfs();
if(res==0)break;
upt(res);
tot+=res;
}
cout<<tot;
return 0;
}
by SIXIANG32 @ 2021-07-08 17:48:58
EK 复杂度假的啊兄弟们
Dinic 才是王道啊兄弟们
by YamadaRyou @ 2021-07-08 19:37:03
@SIXIANG ?EK复杂度是
by SIXIANG32 @ 2021-07-09 08:00:55
@WA王子 我说这道题 EK 过不了啊啊啊啊啊
by YamadaRyou @ 2021-07-09 10:35:00
@SIXIANG az
by Coros_Trusds @ 2021-07-26 17:45:37
@幻离ian
这道题要想笑着AC就必须写 Dinic+弧优化