Irelia

Irelia

逝去的是刀锋,不变的是意志

题解 P1231 【教辅的组成】

posted on 2019-04-24 18:46:09 | under 题解 |

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+当前弧

// 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;
}