题解 P2756 【飞行员配对方案问题】
Ireliaღ
2019-02-08 17:44:23
## 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
*/
```