Irelia

Irelia

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

题解 P2055 【[ZJOI2009]假期的宿舍】

posted on 2019-05-15 16:49:46 | under 题解 |

ISAP最大流

二分图匹配,可以使用最大流

建图

  • 把每个人拆成入点和出点代表学生和房间,第 $i$ 个人入点为 $i$ ,出点为 $n + i$ ,超级原点为 $0$ ,超级会点为 $2n + 1$

  • 对于 $\forall i \in [1, n]$ ,从他的入点向出点连接容量为 $1$ 的边

  • 对于 $\forall i \in \text{{在校生}}$ ,由于他的房间可以被使用,从 $n + i$ 向 $2n + 1$ 连接容量为 $1$ 的边

  • 对于 $\forall i \notin \text{在校生}$ 且 $i \notin \text{回家}$ ,由于 $i$ 需要住宿,从 $0$ 向 $i$ 连接容量为 $1$ 的边

  • 对于 $\forall i, j \in [1, n]$ 满足 $i,j$ 互相认识,从 $i$ 向 $n + j$ 连接容量为 $1$ 的边,从 $j$ 向 $n + i$ 连接容量为 $1$ 的边

最后统计一下最大流是否等于所有需要住宿的学生即可

代码

ISAP挺快的,懒得当前弧优化了

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int MAXN = 55;
const int MAXM = MAXN * MAXN * 4;
const int MAXT = 25;
const int INF = 0x3f3f3f3f;

int T;

namespace Graph{
    int to[MAXM], val[MAXM], nxt[MAXM], head[MAXN << 1], cnt;
    int res, s, t, tot, dep[MAXN << 1], gap[MAXN << 1];

    void Clear() {
        cnt = -1;
        memset(head, -1, sizeof(head));
    }

    void AddEdge(int u, int v, int w) {
        cnt++; to[cnt] = v; val[cnt] = w; nxt[cnt] = head[u]; head[u] = cnt;
        cnt++; to[cnt] = u; val[cnt] = 0; nxt[cnt] = head[v]; head[v] = cnt;
    }

    void Bfs() {
        memset(dep, -1, sizeof(dep));
        memset(gap, 0, sizeof(gap));
        dep[t] = 0; gap[0]++;
        queue<int> q; q.push(t);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = head[u]; ~i; i = nxt[i]) {
                int v = to[i];
                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 (int i = head[u]; ~i; i = nxt[i]) {
            int v = to[i];
            if (val[i] && dep[v] == dep[u] - 1) {
                int mi = Dfs(v, min(val[i], flow - used));
                if (mi) {
                    val[i] -= mi;
                    val[i ^ 1] += mi;
                    used += mi;
                }
                if (used == flow) return used;
            }
        }
        gap[dep[u]]--;
        if (gap[dep[u]] == 0) dep[s] = tot + 1;
        dep[u]++;
        gap[dep[u]]++;
        return used;
    }

    void Isap() {
        res = 0;
        Bfs();
        while (dep[s] <= tot) Dfs(s, INF);
    }
}

int main() {
    ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> T;
    while (T--) {
        Graph :: Clear();
        int n, cnt = 0;
        cin >> n;
        bool flag[n + 1]; memset(flag, false, sizeof(flag));
        Graph :: tot = n * 2 + 2; Graph :: s = 0; Graph :: t = n * 2 + 1;
        for (int i = 1; i <= n; i++) Graph :: AddEdge(i, n + i, 1);
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            if (x == 1) Graph :: AddEdge(n + i, Graph :: t, 1), flag[i] = true;
        }
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            if (x == 0 || !flag[i]) Graph :: AddEdge(Graph :: s, i, 1), cnt++;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int x;
                cin >> x;
                if (x == 1) {
                    Graph :: AddEdge(i, n + j, 1);
                    Graph :: AddEdge(j, n + i, 1);
                }
            }
        }
        Graph :: Isap();
        if (Graph :: res < cnt) cout << "T_T" << endl;
        else cout << "^_^" << endl;
    }
    return 0;
}