题解 P1231 【教辅的组成】
Ireliaღ
2019-04-24 18:46:09
**ISAP最大流+指针存图**
第一眼三分图匹配。但是由于**书不能多次选用**,要对中层进行拆点限制流量。
## 建图
- 设超级原点为$0$,超级汇点为$n_1 \times 2 + n_2 + n_3 + 1$
- 对于$\forall i \in [1, n_1]$,从$i$向$n_1 + i$建立容量为$1$的边
- 对于$\forall i \in [1, n_2]$,从$0$向$n_1 \times 2 + i$建立容量为$1$的边
- 对于$\forall i \in [1, n_3]$,从$n_1 \times 2 + n_2 + i$向$n_1 \times 2 + n_2 + n_3 + 1$建立容量为$1$的边
- 对于可以匹配的$\forall i \in [1, n_2]$,$\forall j \in [1, n_1]$,从$n_1 \times 2 + i$向$j$建立容量为$1$的边
- 对于可以匹配的$\forall i \in [1, n_1]$,$\forall j \in [1, n_3]$,从$n_1 + i$向$n_1 \times 2 + n_2 + j$建立容量为$1$的边
## 代码
ISAP+当前弧
```cpp
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 1e4 + 5;
const int INF = 0x3f3f3f3f;
int n1, n2, n3;
struct Edge{
int to, val;
Edge *nxt, *ops;
Edge(int to, int val, Edge *nxt): to(to), val(val), nxt(nxt) {}
};
Edge *head[MAXN << 2], *cur[MAXN << 2];
void AddEdge(int u, int v, int w) {
head[u] = new Edge(v, w, head[u]);
head[v] = new Edge(u, 0, head[v]);
head[u]->ops = head[v]; head[v]->ops = head[u];
}
int s, t, gap[MAXN << 2], dep[MAXN << 2], res;
void Bfs() {
memset(gap, 0, sizeof(gap));
memset(dep, -1, sizeof(dep));
dep[t] = 0; gap[dep[t]]++;
queue<int> q;
q.push(t);
while (!q.empty()) {
int u = q.front(); q.pop();
for (Edge *e = head[u]; e; e = e->nxt) {
int v = e->to;
if (dep[v] != -1) continue;
dep[v] = dep[u] + 1;
gap[dep[v]]++;
q.push(v);
}
}
}
int Dfs(int u, int flow) {
if (u == t) {
res += flow;
return flow;
}
int used = 0;
for (Edge *&e = cur[u]; e; e = e->nxt) {
int v = e->to;
if (e->val && dep[v] == dep[u] - 1) {
int mi = Dfs(v, min(e->val, flow - used));
if (mi) {
used += mi;
e->val -= mi;
e->ops->val += mi;
}
if (used == flow) return used;
}
}
cur[u] = head[u];
gap[dep[u]]--;
if (gap[dep[u]] == 0) dep[s] = n1 * 2 + n2 + n3 + 3;
dep[u]++;
gap[dep[u]]++;
return used;
}
void Isap() {
res = 0;
Bfs();
memcpy(cur, head, sizeof(head));
while (dep[s] <= n1 * 2 + n2 + n3 + 2) Dfs(s, INF);
}
int main() {
ios :: sync_with_stdio(false); cin.tie(NULL);
cin >> n1 >> n2 >> n3;
s = 0; t = n1 * 2 + n2 + n3 + 1;
int m;
cin >> m;
for (int i = 1; i <= n2; i++) AddEdge(0, n1 * 2 + i, 1);
for (int i = 1; i <= n3; i++) AddEdge(n1 * 2 + n2 + i, t, 1);
for (int i = 1; i <= n1; i++) AddEdge(i, n1 + i, 1);
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
AddEdge(n1 * 2 + y, x, 1);
}
cin >> m;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
AddEdge(n1 + x, n1 * 2 + n2 + y, 1);
}
Isap();
cout << res << endl;
return 0;
}
```