ACM-ICPC 2018 沈阳赛区网络预赛 F. Fantastic Graph(有源上下界最大流 模板)

关于有源上下界最大流: https://blog.csdn.net/regina8023/article/details/45815023

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n, m, k, l, r, s, t, superS, superT;

const int MAXN = ;//点数的最大值

const int MAXM = ;//边数的最大值

const int INF = 0x3f3f3f3f;

struct Edge

{

    int to,next,cap,flow;

} edge[MAXM]; //注意是MAXM

int tol;

int head[MAXN];

void init()

{

    tol = ;

    memset(head,-,sizeof(head));

}

void addedge(int u,int v,int w,int rw = )

{

    edge[tol].to = v;

    edge[tol].cap = w;

    edge[tol].flow = ;

    edge[tol].next = head[u];

    head[u] = tol++;

    edge[tol].to = u;

    edge[tol].cap = rw;

    edge[tol].flow = ;

    edge[tol].next = head[v];

    head[v] = tol++;

}

int Q[MAXN];

int dep[MAXN],cur[MAXN],sta[MAXN];

bool bfs(int s,int t,int n)

{

    int front = ,tail = ;

    memset(dep,-,sizeof(dep[])*(n+));

    dep[s] = ;

    Q[tail++] = s;

    while(front < tail)

    {

        int u = Q[front++];

        for(int i = head[u]; i != -; i = edge[i].next)

        {

            int v = edge[i].to;

            if(edge[i].cap > edge[i].flow && dep[v] == -)

            {

                dep[v] = dep[u] + ;

                if(v == t)

                    return true;

                Q[tail++] = v;

            }

        }

    }

    return false;

}

int dinic(int s,int t,int n)

{

    int maxflow = ;

    while(bfs(s,t,n))

    {

        for(int i = ; i < n; i++)

            cur[i] = head[i];

        int u = s, tail = ;

        while(cur[s] != -)

        {

            if(u == t)

            {

                int tp = INF;

                for(int i = tail-; i >= ; i--)

                    tp = min(tp,edge[sta[i]].cap-edge[sta[i]].flow);

                maxflow += tp;

                for(int i = tail-; i >= ; i--)

                {

                    edge[sta[i]].flow += tp;

                    edge[sta[i]^].flow -= tp;

                    if(edge[sta[i]].cap-edge[sta[i]].flow == )

                        tail = i;

                }

                u = edge[sta[tail]^].to;

            }

            else if(cur[u] != - && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] +  == dep[edge[cur[u]].to])

            {

                sta[tail++] = cur[u];

                u = edge[cur[u]].to;

            }

            else

            {

                while(u != s && cur[u] == -)

                    u = edge[sta[--tail]^].to;

                cur[u] = edge[cur[u]].next;

            }

        }

    }

    return maxflow;

}

int main()

{

    int kase = ;

    while(~scanf("%d %d %d", &m, &n, &k))

    {

        scanf("%d %d", &l,  &r);

        s = n + m + ;

        t = n + m + ;

        superS = n + m + ;

        superT = n + m + ;

        init();

        for(int i = ; i <= k; i++)

        {

            int u, v;

            scanf("%d %d", &u , &v);

            addedge(u, v + n, ); //二分图 建一条容量为1的边

        }

        addedge(t,s,INF); //从汇点向源点建一条inf的边

        for(int i = ; i <= n; i++){

            addedge(s, i, r - l); //从源点向左半图连边

            addedge(superS, i, l);

            addedge(s, superT, l);

        }

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

            int aim = i + n;

            addedge(aim, t, r - l);

            addedge(aim, superT, l);

            addedge(superS, t, l);

        }

        printf("Case %d: ", kase++);

        int ans = dinic(superS, superT, n+m+);

        if(ans == (n+m)*l) puts("Yes");

        else puts("No");

    }

    return ;

}