一般图最大匹配

发表于 更新于 分类于 阅读次数：

一般图最大匹配 比较摸，不是很有学带花树的动力，网上冲浪冲到了随机算法： 首先如果给定的图没有环，直接做类似二分图匹配的匈牙利肯定是对的。如果图中的环都是偶数，增广一下也不会有问题。（二分图就是偶环） 但是如果图中有奇环，可以发现绕环增广会挂掉。。 举个例子，一个大小为$3$的环，选了其中一条边。把环上所有边取反，就冲突了。 那么怎么做呢？可以发现如果可以钦定增广边的时候的顺序，那么其实直接每次把匹配边找出来就行了。 这个顺序不是很清楚，但是我们可以进行多个轮，每次随机一下出边再匹配，随机次数足够多的话有很大的概率是对的。 这里是Hack方法 对随机法进行一些优化：不采用开始前随机，而采用在DFS内部每次随机。每一轮不清空匹配数组。用时间戳优化复杂度。事实证明这样甚至可以过掉UOJ上的Hack数据..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>

inline int rd() {
  int a = 1, b = 0; char c = getchar();
  while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar();
  while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
  return a ? b : -b;
}

const int N = 550;

int n, m, ans[N], vis[N], link[N], cnt, now;

std::vector<int> G[N];

int dfs(int x, int id) {
  vis[x] = id;
  std::random_shuffle(G[x].begin(), G[x].end());
  for (int y : G[x]) {
    int z = link[y];
    if (vis[z] == id)
      continue;
    link[x] = y; link[y] = x;
    link[z] = 0;
    if (!z  dfs(z, id))
      return 1;
    link[y] = z; link[z] = y;
    link[x] = 0;
  }
  return 0;
}

int main() {
  n = rd(), m = rd();
  for (int i = 1; i <= m; ++i) {
    int x = rd(), y = rd();
    G[x].push_back(y);
    G[y].push_back(x);
  }
  srand(time(0));
  for (int i = 1; i <= 5; ++i) {
    memset(vis, 0, sizeof(vis));
    for (int x = 1; x <= n; ++x)
      if (!link[x])
        dfs(x, x);
    int now = 0;
    for (int j = 1; j <= n; ++j)
      now += (bool)(link[j]);
    if (now > cnt) {
      cnt = now;
      for (int j = 1; j <= n; ++j)
        ans[j] = link[j];
    }
  }
  printf("%d\n", cnt / 2);
  for (int i = 1; i <= n; ++i)
    printf("%d ", ans[i]);
  putchar('\n');
  return 0;
}

Update：带花树（真香 随机匹配其实挺好的，就是跑的慢。所以还是需要稳定优秀的Blossom Algorithm。 首先想一下二分图最大匹配是怎么玩的：

  1. 定义增广路。即未匹配边和匹配边交替出现的一条路径。增广路取反后答案+1。
  2. 增广路定理。找不到增广路的时候就是最大匹配。

这两个并不是定义在二分图上的。所以一般图匹配的步骤也是这样的：

  1. 枚举每个点
  2. 找这个点出发的增广路并更新
  3. 枚举下一个点

所以问题就变成了找一个点出发的增广路。考虑对图染色。从一个黑点出发，把路径染成一黑一白的样子。那么图就有三种点：黑，白，未染色。

  1. 考虑搜索路径。如果当前在黑点，并且搜到了一个白点，那么可以直接忽略这个点。
  2. 如果搜到了一个未染色点，考虑这个点是不是匹配点。如果不是匹配点，说明找到了增广路。
  3. 如果是匹配点，那么钦定它是白色，并移动到它匹配的另一个点上，染黑色，继续。
  4. 如果图中存在奇环，会遇到两个黑点相邻的情况。考虑环上有一条到外面的路，发现无论起点是什么颜色，都可以走出去。也就是说环上每个点都应该是黑点。

定义一个$2k+1$大小，$k$条匹配边的奇环为花。花中的未匹配点为花托。因为整个花都是黑点，定义缩花操作为把花缩成一个点。因为每次至少缩两个点，操作次数是线性的。 思路就是这样的，下面说一下算法细节：

  1. BFS遍历图，染色
  2. 找到奇环时，找到两点的LCA，并缩花
  3. 因为有一个遍历的过程，维护pre[]，表示返回时要返回到哪里
  4. 不执行实际的缩花操作，用并查集维护

之后看代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>

const int N = 1e3 + 10;

int n, m, match[N], pre[N], ans;
int col[N], fa[N];
int que[N], head, tail;
std::vector<int> G[N];

int find(int x) {
  return x == fa[x] ? x : fa[x] = find(fa[x]);
}

// 暴力找LCA，交替爬升
inline int get_lca(int x, int y) {
  static int hash[N], hash_cnt;
  ++hash_cnt;
  while (hash[x] != hash_cnt) {
    if (x) hash[x] = hash_cnt, x = find(pre[match[x]]);
    std::swap(x, y);
  }
  return x;
}

// 代码照搬了网上的，1表示白2表示黑
// fa维护的是在哪个花
// 把白点变成黑点并入队
inline void blossom(int x, int y, int p) {
  while (find(x) != p) {
    pre[x] = y;
    fa[y = match[x]] = fa[x] = p;
    if (col[y] == 1)
      col[que[tail++] = y] = 2;
    x = pre[y];
  }
}

inline int bfs(int st) {
  for (int i = 1; i <= n; ++i)
    col[i] = 0, fa[i] = i;
  col[que[tail = 1, head = 0] = st] = 2;
  while (head != tail) {
    int x = que[head++];
    for (int y : G[x]) {
      if (!col[y]) {
        col[y] = 1, pre[y] = x;
        if (!match[y]) {
          // 增广
          while (x) {
            x = match[pre[y]];
            match[match[y] = pre[y]] = y;
            y = x;
          }
          return 1;
        } else
          col[que[tail++] = match[y]] = 2;
      } else if (col[y] == 2 && find(x) != find(y)) {
        // 奇环，缩花
        int p = get_lca(x, y);
        blossom(x, y, p);
        blossom(y, x, p);
      }
    }
  }
  return 0;
}

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1, x, y; i <= m; ++i) {
    scanf("%d %d", &x, &y);
    G[x].push_back(y);
    G[y].push_back(x);
    if (!match[x] && !match[y])
      match[x] = y, match[y] = x, ++ans;
  }
  for (int i = 1; i <= n; ++i)
    if (!match[i] && bfs(i))
      ++ans;
  printf("%d\n", ans);
  for (int i = 1; i <= n; ++i)
    printf("%d ", match[i]);
  putchar('\n');
  return 0;
}