洛谷 P1231教辅的组成

题目描述

/*

s->练习册(1~b)->书(b+1~a+b)->答案(a+b+1~a+b+c)->t

但是可能会有多本练习册指向同一本书，这本书又可能会指向多本答案

这样每本书对答案的贡献就不只是1了，所以考虑对书进行拆点

s->练习册(1~b)->书(b+1~a+b)->(a+b+a~a+a+b)->答案(a+a+b+1~a+a+b+c)->t

*/

#include<iostream>

#include<cstdio>

using namespace std;

const int INF=0x3f3f3f3f;

const int N=1e5+;

struct node{

    int v,f,nxt;

}e[N*];

int m,a,b,c,Enum=,ans,t;

int front[N],cur[N],deep[N];

int q[N];

int qread()

{

    int x=;

    char ch=getchar();

    while(ch<'' || ch>'')ch=getchar();

    while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

    return x;

}

void Insert(int u,int v)

{

    e[++Enum].v=v;

    e[Enum].f=;

    e[Enum].nxt=front[u];

    front[u]=Enum;

    e[++Enum].v=u;

    e[Enum].nxt=front[v];

    front[v]=Enum;

}

bool bfs()

{

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

    {

        deep[i]=;

        cur[i]=front[i];

    }

    int head=,tail=;

    deep[]=;

    q[++tail]=;

    int u;

    while(head<=tail)

    {

        u=q[head++];

        for(int i=front[u];i;i=e[i].nxt)

            if(e[i].f && !deep[e[i].v])

            {

                deep[e[i].v]=deep[u]+;

                if(e[i].v==t)

                    return ;

                q[++tail]=e[i].v;

            }

    }

    return ;

}

int dfs(int now,int cur_flow)

{

    if(now==t)return cur_flow;

    int rest=cur_flow,v;

    for(int &i=cur[now];i;i=e[i].nxt)

    {

        v=e[i].v;

        if(e[i].f && deep[v]==deep[now]+ && rest)

        {

            int new_flow=dfs(v,min(e[i].f,rest));

            e[i].f-=new_flow;

            e[i^].f+=new_flow;

            rest-=new_flow;

            if(!rest)return cur_flow;

        }

    }

    deep[now]=;

    return cur_flow-rest;

}

void Dinic()

{

    while(bfs())

        ans+=dfs(,INF);

    printf("%d\n",ans);

}

int main()

{

    scanf("%d%d%d",&a,&b,&c);

    t=a+a+b+c+;

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

        Insert(,i);

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

        Insert(i+b,i+a+b);

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

        Insert(i+a+a+b,t);

    scanf("%d",&m);

    int u,v;

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

    {

        u=qread();v=qread();

        Insert(v,u+b);

    }

    scanf("%d",&m);

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

    {

        u=qread();v=qread();

        Insert(u+a+b,v+a+a+b);

    }

    Dinic();

    return ;

}