LOJ116 - 有源汇有上下界最大流

原题链接

Description

模板题啦~

Code

//有源汇有上下界最大流

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

inline char gc()

{

    static char now[1<<16],*S,*T;

    if(S==T) {T=(S=now)+fread(now,1,1<<16,stdin); if(S==T) return EOF;}

    return *S++;

}

inline int read()

{

    int x=0; char ch=gc();

    while(ch<'0'||'9'<ch) ch=gc();

    while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=gc();

    return x;

}

int const N=200+10;

int const M=1e4+10;

int const INF=0x7FFFFFFF;

int n,m,s,t;

int flIn[N],s0,t0,flCheck;

int cnt,h[N];

struct edge{int v,c,nxt;} ed[M*3];

void edAdd(int u,int v,int c)

{

    cnt++; ed[cnt].v=v,ed[cnt].c=c,ed[cnt].nxt=h[u],h[u]=cnt;

    cnt++; ed[cnt].v=u,ed[cnt].c=0,ed[cnt].nxt=h[v],h[v]=cnt;

}

int dpt[N]; int q[N],op,cl;

bool bfs()

{

    op=cl=0; memset(dpt,0,sizeof dpt);

    dpt[q[++cl]=s]=1;

    while(op<cl)

    {

        int u=q[++op]; if(u==t) break;

        for(int i=h[u];i;i=ed[i].nxt)

        {

            int v=ed[i].v,c=ed[i].c;

            if(!dpt[v]&&c) dpt[q[++cl]=v]=dpt[u]+1;

        }

    }

    return dpt[t];

}

int fill(int u,int in)

{

    if(u==t||in==0) return in;

    int out=0;

    for(int i=h[u];i;i=ed[i].nxt)

    {

        int v=ed[i].v,c=ed[i].c;

        if(dpt[v]!=dpt[u]+1||!c) continue;

        int fl=fill(v,min(in-out,c));

        if(fl==0) dpt[v]=0;

        else out+=fl,ed[i].c-=fl,ed[i^1].c+=fl;

    }

    return out;

}

int Dinic(int src,int sink)

{

    s=src,t=sink;

    int res=0;

    while(bfs()) res+=fill(s,INF);

    return res;

}

int main()

{

    n=read(),m=read(); int s1=read(),t1=read();

    cnt=1; memset(h,0,sizeof h);

    for(int i=1;i<=m;i++)

    {

        int u=read(),v=read(),f1=read(),f2=read();

        edAdd(u,v,f2-f1); flIn[u]-=f1,flIn[v]+=f1;

    }

    edAdd(t1,s1,INF); s0=n+1,t0=n+2;

    for(int u=1;u<=n;u++)

    {

        if(flIn[u]>0) edAdd(s0,u,flIn[u]),flCheck+=flIn[u];

        if(flIn[u]<0) edAdd(u,t0,-flIn[u]);

    }

    if(Dinic(s0,t0)!=flCheck) printf("please go home to sleep\n");

    else printf("%d\n",Dinic(s1,t1));

    return 0;

}

P.S.

数组开大一点啊…