真·ISAP板子

2019-05-05 20:13:29


#include <cstdio>
#include <cstring>
#include <algorithm>

#define maxn 40105
#define maxe 1000006

using namespace std;

int n1, n2, n3, m1, m2, s, t, ans, lst_add;
int lnk[maxn], son[maxe], w[maxe], nxt[maxe], tot = 1;
int cnt[maxn], dst[maxn], lst[maxn], que[maxn];
bool NAY = true, vis[maxn];

inline int read()
{
    char ch = getchar();
    int ret = 0, f = 1;
    while (ch > '9' || ch < '0')
    {
        if (ch == '-')
            f = -f;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        ret = ret * 10 + ch - '0', ch = getchar();
    return ret * f;
}

inline void adde(int x, int y, int z)
{
    son[++tot] = y, nxt[tot] = lnk[x], lnk[x] = tot, w[tot] = z;
    son[++tot] = x, nxt[tot] = lnk[y], lnk[y] = tot, w[tot] = 0;
}

int isap(int now, int mini)
{
    if (now == t)
    {
        ans += mini;
        return mini;
    }
    int used = 0;
    for (int &j = lst[now]; j; j = nxt[j])
    {
        if (w[j] > 0 && dst[son[j]] + 1 == dst[now])
        {
            int flow = isap(son[j], min(w[j], mini - used));
            if (flow > 0)
            {
                used += flow;
                w[j] -= flow, w[j ^ 1] += flow;
            }
            if (used == mini)
                return used;
        }
    }
    lst[now] = lnk[now];
    --cnt[dst[now]];
    if (cnt[dst[now]] == 0)
        NAY = false;
    ++dst[now];
    ++cnt[dst[now]];
    return used;
}

void BFS(int s)
{
    que[1] = s;
    vis[s] = 1;
    int hed = 0, til = 1;
    while (hed ^ til)
    {
        ++hed;
        for (int j = lnk[que[hed]]; j; j = nxt[j])
        {
            if (vis[son[j]])
                continue;
            dst[son[j]] = dst[que[hed]] + 1;
            que[++til] = son[j];
            vis[son[j]] = 1;
        }
    }
}

int main()
{
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
    n1 = read(), n2 = read(), n3 = read();
    s = 0, t = n1 * 2 + n2 + n3 + 1;
    for (int i = 1; i <= n2; ++i)
        adde(s, n1 * 2 + i, 1);
    for (int i = 1; i <= n3; ++i)
        adde(n1 * 2 + n2 + i, t, 1);
    for (int i = 1; i <= n1; ++i)
        adde(i, n1 + i, 1);
    m1 = read();
    for (int i = 1; i <= m1; ++i)
    {
        int x = read(), y = read();
        adde(n1 * 2 + y, x, 1);
    }
    m2 = read();
    for (int i = 1; i <= m2; ++i)
    {
        int x = read(), y = read();
        adde(n1 + x, n1 * 2 + n2 + y, 1);
    }
    BFS(t);
    memcpy(lst, lnk, sizeof(lnk));
    for (int i = 0; i <= t; ++i)
        ++cnt[dst[i]];
    while (dst[s] <= t + 1 && NAY)
        isap(s, 1 << 30);
    printf("%d\n", ans);
    return 0;
}