题目描述

蒟蒻HansBug在一本语文书里面发现了一本答案，然而他却明明记得这书应该还包含一份练习题。然而出现在他眼前的书多得数不胜数，其中有书，有答案，有练习册。已知一个完整的书册均应该包含且仅包含一本书、一本练习册和一份答案，然而现在全都乱做了一团。许多书上面的字迹都已经模糊了，然而HansBug还是可以大致判断这是一本书还是练习册或答案，并且能够大致知道一本书和答案以及一本书和练习册的对应关系（即仅仅知道某书和某答案、某书和某练习册有可能相对应，除此以外的均不可能对应）。既然如此，HansBug想知道在这样的情况下，最多可能同时组合成多少个完整的书册。

思路

拆点，连边
将每一个书和答案，书和练习冊连起来
因为有重复的，所以要拆点
跑最大流就可以了

#include <stdio.h>
#include <string.h>
#include <queue>
#define maxn 400000
#define min(x,y) x<y?x:y
#define INF 0x7f7f7f7f
#define fill(x,i) memset(x,i,sizeof(x))
using namespace std;
struct edge{int y,w,next;}e[maxn];
int ls[maxn],n,m,maxE=1,S,E,state[maxn];
bool vis[maxn];
inline int read()
{
    int x=0,p=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-')p=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*p;
}
int add(int x,int y,int w)
{
    e[++maxE]=(edge){y,w,ls[x]};
    ls[x]=maxE;
    e[++maxE]=(edge){x,0,ls[y]};
    ls[y]=maxE;
}
int bfs(int x)
{
    queue <int> t;
    t.push(x);
    fill(state,0);
    state[x]=1;
    while (!t.empty())
    {
        int tt=t.front();t.pop();
        for (int i=ls[tt];i;i=e[i].next)
        {
            if (e[i].w>0&&!state[e[i].y])
            {
                state[e[i].y]=state[tt]+1;
                t.push(e[i].y);
                if (e[i].y==E)
                    return true;
            }
        }
    }
    return false;
}
int find(int x,int mn)
{
    if (x==E||!mn) return mn;
    int ret=0;
    for (int i=ls[x];i;i=e[i].next)
        if (state[x]+1==state[e[i].y]&&e[i].w>0)
        {
            int d=find(e[i].y,min(mn-ret,e[i].w));
            e[i].w-=d;
            e[i^1].w+=d;
            ret+=d;
            if (ret==mn) break;
        }
    return ret;
}
int main(void)
{
    int n1=read(),n2=read(),n3=read();
    int m1=read();
    for (int i=1;i<=m1;i++)
    {
        int x=read(),y=read();
        add(y,n2+x,1);
    } 
    int m2=read();
    for (int i=1;i<=m2;i++)
    {
        int x=read(),y=read();
        add(n1+n2+x,n1*2+n2+y,1);
    }
    for (int i=1;i<=n1;i++)
        add(n2+i,n1+n2+i,1);
    S=0;
    E=n1*2+n2+n3+1;
    for (int i=1;i<=n2;i++)
        add(S,i,1);
    for (int i=1;i<=n3;i++)
        add(n1*2+n2+i,E,1);
    int ans=0;
    while (bfs(S))
        ans+=find(S,INF);
    printf("%d\n",ans);
}