分析
-
本题就是让求图的最大匹配,使用匈牙利算法的时间复杂度是 $O(n \times m)$,使用
dinic
算法的时间复杂度是 $O(\sqrt{n} \times m)$。 -
使用最大流算法需要考虑如何建图,可以建立一个虚拟源点
S
和虚拟汇点T
。然后让S
指向所有的外籍飞行员,边权为1;让所有英国籍飞行员指向汇点T
,边权为1,这样原图的最大匹配问题就转化为了新图的最大流问题(证明略)。 -
考虑新图中需要建的边数,因为
m+n
最大为100,因此如果两者都为50的话,一共2500条边,加上新加的边,一共2600条,考虑反向边,因此需要5200条边。 -
最后需要考虑如何输出匹配结果,可以遍历新图中所有正向边,如果正向边指向的点的编号在
[m+1, n]
之间并且对应的边流量是1(对应残留网络中容量f为0),输出这条边即可。
代码
- C++
// dinic算法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110, M = 5210, INF = 1e8;
int m, n, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
void add(int a, int b, int c) {
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;
e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}
bool bfs() {
int hh = 0, tt = 0;
memset(d, -1, sizeof d);
q[0] = S, d[S] = 0, cur[S] = h[S];
while (hh <= tt) {
int t = q[hh++];
for (int i = h[t]; ~i; i = ne[i]) {
int ver = e[i];
if (d[ver] == -1 && f[i]) {
d[ver] = d[t] + 1;
cur[ver] = h[ver];
if (ver == T) return true;
q[++tt] = ver;
}
}
}
return false;
}
int find(int u, int limit) {
if (u == T) return limit;
int flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
cur[u] = i;
int ver = e[i];
if (d[ver] == d[u] + 1 && f[i]) {
int t = find(ver, min(f[i], limit - flow));
if (!t) d[ver] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic() {
int r = 0, flow;
while (bfs()) while (flow = find(S, INF)) r += flow;
return r;
}
int main() {
scanf("%d%d", &m, &n);
S = 0, T = n + 1;
memset(h, -1, sizeof h);
for (int i = 1; i <= m; i++) add(S, i, 1);
for (int i = m + 1; i <= n; i++) add(i, T, 1);
int a, b;
while (scanf("%d%d", &a, & b), a != -1) add(a, b, 1);
printf("%d\n", dinic());
for (int i = 0; i < idx; i += 2)
if (e[i] > m && e[i] <= n && !f[i])
printf("%d %d\n", e[i ^ 1], e[i]);
return 0;
}
// 匈牙利算法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110, M = 5010, INF = 1e8;
int m, n;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool find(int x) {
for (int i = h[x]; ~i; i = ne[i]) {
int j = e[i];
if (!st[j]) {
st[j] = true;
if (match[j] == 0 || find(match[j])) {
match[j] = x;
return true;
}
}
}
return false;
}
int main() {
scanf("%d%d", &m, &n);
memset(h, -1, sizeof h);
int a, b;
while (scanf("%d%d", &a, & b), a != -1) add(a, b), add(b, a);
// 匈牙利算法
int res = 0;
for (int i = m + 1; i <= n; i++) { // 遍历所有的英国籍飞行员
memset(st, 0, sizeof st);
if (find(i)) res++;
}
printf("%d\n", res);
for (int i = 1; i <= m; i++)
if (match[i])
printf("%d %d\n", i, match[i]);
return 0;
}