真·ISAP板子
吹雪吹雪吹
2019-05-05 20:13:29
```cpp
#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;
}
```