题解 P2756 【飞行员配对方案问题】

Ireliaღ

2019-02-08 17:44:23

Solution

## ISAP二分图匹配 看到二分图匹配直接上$ISAP$,吊打匈牙利 ### 前置知识:ISAP最大流算法 按照惯例放学长博客 **[传送门](https://www.cnblogs.com/ubospica/p/9974285.html)** ### 建图 (1) 以$0$为超级源点,$n + 1$为超级汇点,从$0$向$1$到$m$的所有点建立容量为$1$的边,从$m + 1$到$n$的所有点向$n + 1$建立容量为$1$的边 (2) 对于每一对匹配$match_{i,j}$,从$i$到$j$建立容量为$1$的边 ### 代码 正常$ISAP$从超级源点到超级汇点跑最大流,加当前弧优化直接起飞 ***代码如下(习惯性$O3$)*** 普通版 ```cpp #pragma GCC optimize(3) #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using std::queue; const int MAXN = 105; const int INF = 0x3f3f3f3f; struct Edge{ int to, val; Edge *next, *ops; Edge(int to, int val, Edge *next):to(to), val(val), next(next){} }; Edge *head[MAXN]; int n, m; 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[from]->ops = head[to]; head[to]->ops = head[from]; } namespace ISAP{ int s, t, maxflow; int dep[MAXN], gap[MAXN]; 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 = head[u]; e; e = e->next) { int v = e->to; if (e->val && dep[v] == dep[u] - 1) { int mi = Dfs(v, std::min(e->val, flow - used)); if (mi) { used += mi; e->val -= mi; e->ops->val += mi; if (used == flow) return used; } } } gap[dep[u]]--; if (gap[dep[u]] == 0) dep[s] = n + 3; dep[u]++; gap[dep[u]]++; return used; } void Work() { maxflow = 0; Bfs(); while (dep[s] < n + 2) Dfs(s, INF); } void Print() { if (maxflow == 0) { puts("No Solution!"); return; } printf("%d\n", maxflow); for (int i = 1; i <= m; i++) { for (Edge *e = head[i]; e; e = e->next) { int v = e->to; if (v > m && v <= n && e->val == 0) printf("%d %d\n", i, v); } } } } int main() { scanf("%d %d", &m, &n); ISAP::s = 0; ISAP::t = n + 1; memset(head, 0, sizeof(head)); for (int i = 1; i <= m; i++) { AddEdge(0, i, 1); } for (int i = m + 1; i <= n; i++) { AddEdge(i, n + 1, 1); } int x, y; while (scanf("%d %d", &x, &y), x != -1 && y != -1) { AddEdge(x, y, 1); } ISAP::Work(); ISAP::Print(); return 0; } /* 5 10 1 7 1 8 2 6 2 9 2 10 3 7 3 8 4 7 4 8 5 10 -1 -1 */ ``` 优化版 ```cpp #pragma GCC optimize(3) #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using std::queue; const int MAXN = 105; const int INF = 0x3f3f3f3f; struct Edge{ int to, val; Edge *next, *ops; Edge(int to, int val, Edge *next):to(to), val(val), next(next){} }; Edge *head[MAXN]; int n, m; 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[from]->ops = head[to]; head[to]->ops = head[from]; } namespace ISAP{ int s, t, maxflow; int dep[MAXN], gap[MAXN]; Edge *cur[MAXN]; 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 (e->val && dep[v] == dep[u] - 1) { int mi = Dfs(v, std::min(e->val, flow - used)); if (mi) { used += mi; e->val -= mi; e->ops->val += mi; if (used == flow) return used; } } } gap[dep[u]]--; cur[u] = head[u]; if (gap[dep[u]] == 0) dep[s] = n + 3; dep[u]++; gap[dep[u]]++; return used; } void Work() { for (int i = 0; i <= n; i++) cur[i] = head[i]; maxflow = 0; Bfs(); while (dep[s] < n + 2) Dfs(s, INF); } void Print() { if (maxflow == 0) { puts("No Solution!"); return; } printf("%d\n", maxflow); for (int i = 1; i <= m; i++) { for (Edge *e = head[i]; e; e = e->next) { int v = e->to; if (v > m && v <= n && e->val == 0) printf("%d %d\n", i, v); } } } } int main() { scanf("%d %d", &m, &n); ISAP::s = 0; ISAP::t = n + 1; memset(head, 0, sizeof(head)); for (int i = 1; i <= m; i++) { AddEdge(0, i, 1); } for (int i = m + 1; i <= n; i++) { AddEdge(i, n + 1, 1); } int x, y; while (scanf("%d %d", &x, &y), x != -1 && y != -1) { AddEdge(x, y, 1); } ISAP::Work(); ISAP::Print(); return 0; } /* 5 10 1 7 1 8 2 6 2 9 2 10 3 7 3 8 4 7 4 8 5 10 -1 -1 */ ```