题解 P1894 【[USACO4.2]完美的牛栏The Perfect Stall】
Ireliaღ
2019-02-03 17:32:37
## 一个带当前弧优化的$ISAP$题解
### 题目大意
有$n$个牛，$m$个牛棚，每头牛有多个可选择的牛棚，求出让尽可能多的牛住进牛棚
### 前置知识：ISAP算法
可以看~~pica~~学长的[博客](https://www.cnblogs.com/ubospica/p/9974285.html)
### 思路
二分图匹配，可以用最大流，我选择用$ISAP$跑最大流，速度快
### 建图
(1) 把$0$当做超级源点，向从$1$到$n$所有点建立容量为$1$的边，把$n + m + 1$当做超级汇点，从$n + 1$到$n + m$向它建立容量为$1$的边
(2) 对于牛$i$的所有选择$x_1$到$x_s$，从$i$到$n + x_j$建立容量为$1$的边
### 输出
跑$ISAP$，直接输出最大流
### 代码（有当前弧优化）
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using std::queue;
const int MAXN = 205;
const int MAXM = 205;
const int INF = 0x3f3f3f3f;
int n, m;
struct Edge{
int to, val;
Edge *next, *opps;
Edge(int to, int val, Edge* next):to(to), val(val), next(next){}
};
Edge *head[MAXN + MAXM];
void AddEdge(int from, int to, int val) {
head[from] = new Edge(to, val, head[from]);
head[to] = new Edge(from, 0, head[to]);
head[to]->opps = head[from]; head[from]->opps = head[to];
}
namespace ISAP{
Edge *cur[MAXN + MAXM];
int dep[MAXN + MAXM], gap[MAXN + MAXM];
int s, t, maxflow = 0;
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->next) {
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) {
maxflow += flow;
return flow;
}
int used = 0;
for (Edge *&e = cur[u]; e; e = e->next) {//当前弧优化，需要取址修改当前弧
int v = e->to;
if (dep[v] == dep[u] - 1 && e->val) {
int mi = Dfs(v, std::min(flow - used, e->val));
if (mi) {
used += mi;
e->val -= mi;
e->opps->val += mi;
if (used == flow) return flow;
}
}
}
gap[dep[u]]--;
if (gap[dep[u]] == 0) dep[s] = n + 1;
dep[u]++;
gap[dep[u]]++;
cur[u] = head[u];//复原当前弧
return used;
}
void Work() {
for (int i = 0; i <= n + m + 1; i++) cur[i] = head[i];
maxflow = 0;
Bfs();
while (dep[s] < n) Dfs(s, INF);
}
}
int main() {
memset(head, 0, sizeof(head));
scanf("%d %d", &n, &m);
ISAP::s = 0; ISAP::t = n + m + 1;
for (int i = 1; i <= n; i++) AddEdge(0, i, 1);
for (int i = 1; i <= m; i++) AddEdge(n + i, n + m + 1, 1);
for (int i = 1, p; i <= n; i++) {
scanf("%d", &p);
for (int j = 1, x; j <= p; j++) {
scanf("%d", &x);
AddEdge(i, n + x, 1);
}
}
ISAP::Work();
printf("%d\n", ISAP::maxflow);
return 0;
}
/*
5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2
*/
```
由于我是个懒人，不愿意算最多有多少条边，所以使用了极其拖慢时间的$new$函数动态开空间建边。但是即使这样，也只跑了$26ms$，说明$ISAP$的效率很高