Tari @ 2019-04-15 19:37:45
rt
(怀疑自己是不是好几次这样)
https://www.luogu.org/recordnew/show/18240528
建议加强数据。。。(要不遗憾终生,跟自己学会了似的)
// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define R register int
#define getchar() *S++
const int Inf=0x3f3f3f3f,N=10010,M=200010;
char RR[500000005],*S=RR;
using namespace std;
inline int g() {
R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
}
int n,m,s,t,cnt,mx,fl;//cnt没有初始化成1
int vr[M],w[M],nxt[M],fir[N],incf[N],d[N];
queue<int>q;
inline void add(int u,int v,int ww) {
vr[++cnt]=v,w[cnt]=ww,nxt[cnt]=fir[u],fir[u]=cnt;
vr[++cnt]=u,w[cnt]=0,nxt[cnt]=fir[u],fir[u]=cnt;//什么垃圾加边fir[u]=cnt?fir[v]=cnt
}
inline bool bfs() {
memset(d,0,sizeof(d)); while(q.size()) q.pop();
q.push(s); d[s]=1;
while(q.size()) { R u=q.front(); q.pop();
for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
if(w[i]&&!d[v]) {
q.push(v),d[v]=d[u]+1;
if(v==t) return true;
}
}
} return false;
}
inline int dinic(int u,int fl) {
if(u==t) return fl; R res=fl;
for(R i=fir[u];i&&res;i=nxt[i]) { R v=vr[i];
if(w[i]&&d[v]==d[u]+1) {
R k=dinic(v,min(res,w[i]));
if(!k) d[v]=0;
w[i]-=k,w[i^1]+=k,res-=k;
}
} return fl-res;
}
signed main() {
fread(RR,1,sizeof(RR),stdin);
n=g(),m=g(),s=g(),t=g();
for(R i=1,u,v,w;i<=m;++i) u=g(),v=g(),w=g(),add(u,v,w);
while(bfs()) while(fl=dinic(s,Inf)) mx+=fl;
printf("%d\n",mx);
}
by Tari @ 2019-04-15 19:38:16
打代码千万要认真。。。
by ywy_c_asm @ 2019-04-15 19:56:28
@Jackpei 这题数据水的一批……各种错误写法都能过……
by nofind @ 2019-04-15 19:56:40
@showice1984
by Tari @ 2019-04-15 19:57:51
@ywy_c_asm好吧
by i207M @ 2019-04-15 19:59:15
@Jackpei 这题数据水的一批……各种错误写法都能过……
by grhsmt @ 2019-07-03 15:57:31
@i207M 好像EK被卡死了。
by i207M @ 2019-07-03 17:50:32
指正:dinic的错误写法