「Luogu P2055」「ZJOI2009」假期的宿舍

Description

$T$ 组数据。给定 $n$ 个人和若干人际关系，有些人有床。如果某两人 $A,B$ 互相认识且 $B$ 有床，则 $A$ 可以睡 $B$ 的床，自己也可以睡自己的床。求能否让所有指定的人都有床睡。$(1 \leq n \leq 50,1 \leq T \leq 20)$

Source

[Luogu]P2055

Solution

考虑建立一个 二分图 模型。

左部点表示不回家的学生（晚上要留宿），右部点表示在校学生（这些学生有床），接着对于左部点 $A$ 与右部点 $B$，若 $A,B$ 互相认识，则在它们之间连一条边，表示 $A$ 可以睡 $B$ 的床。不要忘记自己与自己连边，因为自己可以睡自己的床。最后判断最大匹配是否为左部点的数量即可。

网络流 模型同理，最后跑一遍 $\rm dinic$ 最大流也同样能得到答案。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

const int MAXN = 100, MAXM = 1e4, INF = 0x3f3f3f3f;
int t, n, tot, head[MAXN + 5], cur[MAXN + 5], depth[MAXN + 5];
bool atsch[MAXN + 5], leave[MAXN + 5];
struct Edge {
    int next, to, dis;    
} e[MAXM + 5];

inline void addEdge(int u, int v, int w) {
    e[++tot] = (Edge) { head[u], v, w };
    head[u] = tot;
}

inline bool bfs(int s, int t) {
    for (int i = 0; i <= t; ++i) cur[i] = head[i];
    memset(depth, 0, sizeof (depth));
    queue<int> q;
    depth[s] = 1;
    q.push(s);
    for (; !q.empty(); ) {
        int u = q.front();
        q.pop();
        for (int v, w, i = head[u]; v = e[i].to, w = e[i].dis, i && rest; i = e[i].next) {
            if (depth[v] || !w) continue;
            depth[v] = depth[u] + 1;
            if (v == t) return 1;
            q.push(v);
        }
    }
    return 0;
}

int dinic(int u, int t, int flow) {
    if (u == t) return flow;
    int rest = flow;
    for (int v, w, i = cur[u]; v = e[i].to, w = e[i].dis, i; i = e[i].next) {
        cur[u] = i;//当前弧优化 
        if (depth[v] != depth[u] + 1 || !w) continue;
        int k = dinic(v, t, min(rest, w));
        if (!k) depth[v] = 0;
        else {
            e[i].dis -= k;
            e[i ^ 1].dis += k;
            rest -= k;
        }
    }
    return flow - rest;
}

inline int maxFlow(int s, int t) {
    int res = 0;
    for (; bfs(s, t); ) res += dinic(s, t, INF);
    return res;
}

int main() {
    for (read(t); t; --t) {
        read(n);
        tot = 1;//清空
        memset(head, 0, sizeof (head));
        int cnt = 0, s = 0, t = 2 * n + 1;
        for (int i = 1; i <= n; ++i) {
            read(atsch[i]);//是否在校 
            if (atsch[i])
                addEdge(i + n, t, 1), addEdge(t, i + n, 0);//连向汇点 
        }
        for (int i = 1; i <= n; ++i) {
            read(leave[i]);//是否回家 
            if (!(leave[i] && atsch[i])) {//在校学生
                addEdge(s, i, 1), addEdge(i, s, 0);//连向源点 
                ++cnt;//在校学生数量 
            }
        }
        for (int i = 1; i <= n; ++i)
            for (int x, j = 1; j <= n; ++j) {
                read(x);
                if (i == j || x)//互相认识，或自己和自己连边 
                    addEdge(i, j + n, 1), addEdge(j + n, i, 0);
            }
        puts(maxFlow(s, t) == cnt ? "^_^" : "T_T");
    }
    return 0;
}