Into_qwq @ 2020-08-05 17:21:19
RT,求大佬们抽出少许时间帮助我这只蒟蒻/kel
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500010;
const ll inf=2005020000;
int n,m,s,t,u,v,book[3000][3000],pre[N],head[N],cnt=1;
bool vis[N];
ll w,ans,dis[N];
queue <int> q;
struct edge{
int to,nex;
ll val;
}e[N];
inline void add(int a,int b,ll c){
e[++cnt].to=b;
e[cnt].val=w;
e[cnt].nex=head[a];
head[a]=cnt;
}
inline bool bfs(){
memset(vis,0,sizeof(vis));
while(q.size()) q.pop();
q.push(s);vis[s]=1;
dis[s]=inf;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i;i=e[i].nex){
if(!e[i].val) continue;
int to=e[i].to;
if(vis[to]) continue;
dis[to]=min(dis[x],e[i].val);pre[to]=i;
vis[to]=1;q.push(to);
if(to==t) return 1;
}
}
return 0;
}
inline void update(){
int a=t;
while(a!=s){
int b=pre[a];
e[b].val-=dis[t];
e[b^1].val+=dis[t];
a=e[b^1].to;
}
ans+=dis[t];
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
while(m--){
cin>>u>>v>>w;
if(!book[u][v]) add(u,v,w),add(v,u,0),book[u][v]=cnt;
else e[book[u][v]-1].val+=w;
}
while(1)
if(bfs()) update();
else break;
printf("%lld\n",ans);
return 0;
}
record:https://www.luogu.com.cn/record/36378093
by Prean @ 2020-08-05 17:27:21
EK爬爬爬,这道题还卡EK
基本上所有网络流题都卡EK
by FunnyCreatress @ 2020-08-05 17:34:34
inline void add(int a,int b,ll c){
e[++cnt].to=b;
e[cnt].val=w;//???
e[cnt].nex=head[a];
head[a]=cnt;
}
你反向边建了个寂寞
by FunnyCreatress @ 2020-08-05 17:34:43
@IamnotTXN
by Into_qwq @ 2020-08-05 17:38:58
谢谢
by Into_qwq @ 2020-08-05 17:39:30
我好想忘记该参数了(不过怎么AC了这么多点)
by Prean @ 2020-08-05 17:42:38
@FunnyCreatress 他主函数建了反向边。。。
by Into_qwq @ 2020-08-05 17:44:47
是我传参出了问题/kk
by Into_qwq @ 2020-08-05 17:47:06
@FunnyCreatress AC了,谢谢大佬orz
by FunnyCreatress @ 2020-08-05 17:54:55
@limaopipi2022 不是建了寂寞,他反向边建了一条容量为
by 聪明的猪 @ 2020-10-27 20:43:17
话说回来,EK建边最好还是用邻接矩阵好一点(毕竟邻接矩阵存不下的图EK肯定也跑不动x)