我是怎么AC的

P3376 【模板】网络最大流

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的错误写法


|