Dinic:
```
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define mst(a,b) memset(a,b,sizeof(a))
#define For(i, k, j) for(int i = (k); i <= (j); i++)
#define INF 2147483647/3
#define ll long long
using namespace std;
inline int read()
{
int num = 0, flag = 1;
char c=' ';
for(;c>'9'||c<'0';c=getchar()) if(c=='-') flag = -1;
for(;c>='0'&&c<='9';num=(num<<1)+(num<<3)+c-48,c=getchar());
return num * flag;
}
const int MAX_M = 150005;
const int MAX_N = 100005;
struct edge {
int v, c, nxt;
} e[MAX_M];
int p[MAX_N], eid;
void init() {
memset(p, -1, sizeof(p));
eid = 0;
}
void insert(int u, int v, int c) {
e[eid].v = v;
e[eid].nxt = p[u];
e[eid].c = c;
p[u] = eid++;
}
void addedge(int u, int v, int c) {
insert(u, v, c);
insert(v, u, 0);
}
int S, T;
int d[MAX_N];
bool bfs() {
memset(d, -1, sizeof(d));
queue<int> q;
q.push(S);
d[S] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = p[u]; i != -1; i = e[i].nxt) {
int v = e[i].v;
if (e[i].c > 0 && d[v] == -1) {
q.push(v);
d[v] = d[u] + 1;
}
}
}
return (d[T] != -1);
}
int dfs(int u, int flow) {
if (u == T) {
return flow;
}
int res = 0;
for (int i = p[u]; i != -1; i = e[i].nxt) {
int v = e[i].v;
if (e[i].c > 0 && d[u] + 1 == d[v]) {
int tmp = dfs(v, min(flow, e[i].c));
flow -= tmp;
e[i].c -= tmp;
res += tmp;
e[i ^ 1].c += tmp;
if (flow == 0) {
break;
}
}
}
if (res == 0) {
d[u] = -1;
}
return res;
}
int Dinic() {
int res = 0;
while (bfs()) {
res += dfs(S, INF);
}
return res;
}
int main()
{
init();
int n1 = read(), n2 = read(), n3 = read();
S = 1, T = 1+n1+n1+n2+n3+1;
For(i, 1, n2) {
addedge(S, i+1, 1);
}
For(i, 1, n3) {
addedge(1+n2+2*n1+i, T, 1);
}
For(i, 1, n1) {
addedge(1+n2+i, 1+n2+n1+i, 1);
}
int m1 = read() ;
For(i, 1, m1) {
int u = read(), v = read();
addedge(v+1, u+n2+1, 1);
}
int m2 = read();
For(i, 1, m2) {
int u = read(), v = read();
addedge(1+n2+n1+u, 1+n2+n1+n1+v, 1);
}
printf("%d\n", Dinic());
return 0;
}
```
by YLWang @ 2019-02-24 11:52:06
orz wyl
我都不会ISAP /kel
by Dilute @ 2019-02-24 12:26:02