题解 P2055 【[ZJOI2009]假期的宿舍】
Ireliaღ
2019-05-15 16:49:46
**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挺快的，懒得当前弧优化了
```cpp
// 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;
}
```