题解 P1402 【酒店之王】
Ireliaღ
2019-05-14 14:06:51
**ISAP最大流**
刚做完[一道题](https://www.luogu.org/problemnew/show/P1231)，发现这道题跟它一样，稍微改改就A了
简单地说，三分图匹配，需要对中间一层进行拆点来防止重复选择。
## 建图
- 设有$n_1$个人，$n_2$个房间，$n_3$个菜品
- 设超级原点为$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已经挺快了。
```cpp
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 105;
int n, m1, m2;
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];
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 dep[MAXN << 2], gap[MAXN << 2], res, s, t;
void Bfs() {
memset(dep, -1, sizeof(dep));
memset(gap, 0, sizeof(gap));
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 = head[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) {
e->val -= mi;
e->ops->val += mi;
used += mi;
}
if (used == flow) return used;
}
}
gap[dep[u]]--;
if (gap[dep[u]] == 0) dep[s] = n + n + m1 + m2 + 3;
dep[u]++;
gap[dep[u]]++;
return used;
}
void Isap() {
res = 0;
Bfs();
while (dep[s] <= n + n + m1 + m2 + 3) Dfs(s, INF);
}
int main() {
cin >> n >> m1 >> m2;
s = 0; t = n + n + m1 + m2 + 1;
for (int i = 1; i <= n; i++) AddEdge(m1 + i, m1 + n + i, 1);
for (int i = 1; i <= m1; i++) AddEdge(s, i, 1);
for (int i = 1; i <= m2; i++) AddEdge(m1 + n + n + i, t, 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m1; j++) {
int x;
cin >> x;
if (x == 1) AddEdge(j, m1 + i, 1);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m2; j++) {
int x;
cin >> x;
if (x == 1) AddEdge(m1 + n + i, m1 + n + n + j, 1);
}
}
Isap();
cout << res << endl;
return 0;
}
```