题解 P1231 【教辅的组成】

Ireliaღ

2019-04-24 18:46:09

Solution

**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; } ```