幻离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:28:23
@幻离ian EK 这道题会被卡吧
而且显然你用邻接矩阵存图跑一遍 dfs 就差不多 n 方肯定过不了了啊
by 幻离ian @ 2021-07-08 17:34:09
旁边的人用EK过了
by Rolling_L @ 2021-07-08 17:35:19
@SIXIANG
这题n不是200吗,n方应该能过吧
by 幻离ian @ 2021-07-08 17:35:21
@SIXIANG
代码基本相似
https://www.luogu.com.cn/record/52609961
by SIXIANG32 @ 2021-07-08 17:39:28
@ytl_jr 要跑多变 bfs 嗷嗷嗷嗷嗷啊
by SIXIANG32 @ 2021-07-08 17:40:14
@幻离ian 我记得我看过有人用 EK 做的,用 vector 存图,然后用邻接矩阵存边权,记得判重边
我记得好像是这样的,如果说错了勿喷
by Rolling_L @ 2021-07-08 17:42:25
@SIXIANG
多遍bfs时间大约为而且那份AC代码是我写的
by SIXIANG32 @ 2021-07-08 17:44:28
@ytl_jr 哦
不是 lz 的 bfs 是 n ^ 2 的啊
但我的意思真的不是这个算法是 n ^ 2 的啊啊啊啊啊
还有好好写 Dinic 不香吗,我记得草地排水就可以用 EK 过,为啥不写那题啊(
by 幻离ian @ 2021-07-08 17:47:33
@SIXIANG
我也用星向图写了一遍,也卡这两个点,而且查出来是卡while了
https://www.luogu.com.cn/record/52610405
by SIXIANG32 @ 2021-07-08 17:48:32
@幻离ian 不是他可能有重边啊啊啊啊啊
听说判了重边以后就行了
具体怎么搞我记得有一篇题解有些,但我写的是 Dinic(