Amazon.co.jp： 組合せ最適化-理論とアルゴリズム: B. コルテ, J. フィーゲン, 浅野 孝夫, 平田 富夫, 小野 孝男, 浅野 泰仁: 本

にのっているアルゴリズム．

をそのまま実装しただけ．

長くなってしまった．

奇閉路をきりだすのが結構メンドウ．

バグあるかも． 

#include <iostream>
#include <vector>
using namespace std;
#define REP(i,n) for(int i = ; i < (int)(n); ++i)
#define FOR(i,c) for (__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define NODE(i,v,path) for (int i = , v = path[i]; v >= ; v = path[++i])
const int N = 100;
int n, mu[N], phi[N], rho[N], pathX[N], pathY[N];
bool scan[N], visitX[N], visitY[N];
vector< vector<int> > neighbor(N, vector<int>());
inline bool even(int x) { return mu[x] == x || phi[mu[x]] != mu[x]; }
inline bool odd(int x) { return mu[x] != x && phi[mu[x]] == mu[x] && phi[x] != x; }
inline bool out(int x) { return mu[x] != x && phi[mu[x]] == mu[x] && phi[x] == x; }
bool scanAllEven(int &x) {
for (; x < n; ++x) if ( !scan[x] && even(x) ) return false;
return true;
}
bool adjacent(int x, int &y) {
FOR(z,neighbor[x]) if (out(*z) || (even(*z) && rho[*z] != rho[x])) { y = *z; return true;}
return false;
}
bool disjointPath(int x, int y, int &r) {
REP(v,N) pathX[v] = pathY[v] = -1;
REP(v,N) visitX[v] = visitY[v] = false;
for (int i = , v = x; !visitX[v]; ++i) pathX[i] = v, visitX[v] = true, v = i%2 ? phi[v]: mu[v];
for (int i = , v = y; !visitY[v]; ++i) pathY[i] = v, visitY[v] = true, v = i%2 ? phi[v]: mu[v];
for (int i = ; pathX[i] >= ; ++i) {
if (!visitY[pathX[i]]) continue;
r = pathX[i];
for (++i; pathX[i] >= ; ++i) visitX[pathX[i]] = false, pathX[i] = -1;
for (i=; pathY[i] != r; ++i);
for (++i; pathY[i] >= ; ++i) visitY[pathY[i]] = false, pathY[i] = -1;
return false;
}
return true;
}
void augment(int &x, int y) {
NODE(i,v,pathX) if (i%2) mu[phi[v]] = v, mu[v] = phi[v];
NODE(i,v,pathY) if (i%2) mu[phi[v]] = v, mu[v] = phi[v];
mu[x] = y, mu[y] = x;
REP(v,n) phi[v] = rho[v] = v, scan[v] = false;
}
void shrink(int x, int y, int r) {
NODE(i,v,pathX) if (i%2 && rho[phi[v]] != r) phi[phi[v]] = v;
NODE(i,v,pathY) if (i%2 && rho[phi[v]] != r) phi[phi[v]] = v;
if (rho[x] != r) phi[x] = y;
if (rho[y] != r) phi[y] = x;
REP(v,n) if(visitX[rho[v]] || visitY[rho[v]]) rho[v] = r;
}
void matching() {
REP(v,N)
mu[v] = phi[v] = rho[v] = v, scan[v] = false;
int x = , y ,r;
while (!scanAllEven(x)) {
if (!adjacent(x,y)) scan[x] = true, x = ;
else if (out(y)) phi[y] = x; // grow
else if (disjointPath(x,y,r)) augment(x, y), x = ;
else shrink(x,y,r);
}
}

こんなふうに使う． 

int main() {
n = 15;
addEdge(1,2);
addEdge(2,3);
addEdge(2,13);
addEdge(2,14);
addEdge(3,4);
addEdge(3,6);
addEdge(4,5);
addEdge(4,10);
addEdge(5,8);
addEdge(5,7);
addEdge(6,7);
addEdge(6,10);
addEdge(8,9);
addEdge(8,13);
addEdge(8,14);
addEdge(10,12);
addEdge(11,12);
cout << "#Graph#" << endl;
REP(i,n) {
cout << i << " -> " ;
FOR(j,neighbor[i]) cout << *j << " ";
cout << endl;
}
matching();
cout << "#Matching#" << endl;
REP(i,n) if (i < mu[i]) cout << i << " -- " << mu[i] << endl;
}

出力． 

#Graph#
0 ->
1 -> 2
2 -> 1 3 13 14
3 -> 2 4 6
4 -> 3 5 10
5 -> 4 8 7
6 -> 3 7 10
7 -> 5 6
8 -> 5 9 13 14
9 -> 8
10 -> 4 6 12
11 -> 12
12 -> 10 11
13 -> 2 8
14 -> 2 8
#Matching#
1 -- 2
3 -- 6
4 -- 10
5 -- 7
8 -- 9
11 -- 12