「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$ 最大流也同样能得到答案。

VQ8GKe.png

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#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;
}

本文标题:「Luogu P2055」「ZJOI2009」假期的宿舍

文章作者:Heartlessly

发布时间:2019年05月31日 - 08:02:09

最后更新:2019年05月31日 - 18:43:55

原始链接:https://heartlessly.github.io/problems/luogu-p2055/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%