match.cc

三个求二分图最大匹配的程序（bfs

int nx, ny, g[maxn][maxn], cx[maxn], cy[maxn];
// cx[i]表示与Xi匹配的Y顶点, cy[i]同理

1、DFS增广, 适用稠密图, O(n^3)
int mk[maxn];
int path(int u){
    for (int v = 0; v < ny; v++) if (g[u][v] && !mk[v]){
        mk[v] = 1; if (cy[v] == -1 || path(cy[v])) { cx[u] = v; cy[v] = u; return 1; }
    } return 0;
}
int MaxMatch(){
    int res(0);
    memset(cx, 0xff, sizeof(cx)); memset(cy, 0xff, sizeof(cy));
    for (int i = 0; i < nx; i++) if (cx[i] == -1) { memset(mk, 0, sizeof(mk)); res += path(i); }
    return res;
}

2、BFS增广, 适用稀疏图, O(n^3)
int pred[maxn], mk[maxn], open[maxn];
int MaxMatch()
{
    int i, u, v, t, d, e, cur, tail, res(0);
    memset(mk, 0xff, sizeof(mk)); memset(cx, 0xff, sizeof(cx)); memset(cy, 0xff, sizeof(cy));
    for (i = 0; i < nx; i++){
        pred[i] = -1;
        for (open[cur = tail = 0] = i; cur <= tail && cx[i] == -1; cur++){
            for (u = open[cur], v = 0; v < ny && cx[i] == -1; v ++) if (g[u][v] && mk[v] != i){
                mk[v] = i; open[++tail] = cy[v]; if (open[tail] >= 0) { pred[open[tail]] = u; continue; }
                for (d = u, e = v; d != -1; t = cx[d], cx[d] = e, cy[e] = d, e = t, d = pred[d]);
                break;
            }
        }
        if (cx[i] != -1) res++;
    }
    return res;
}

3、多增广路, O(n^2.5)
int pred[maxn], mk[maxn], open[maxn], src[maxn];
int MaxMatch(){
    int i, u, v, t, d, e, cur, tail, res(0), p, flag;
    memset(mk, 0xff, sizeof(mk)); memset(cx, 0xff, sizeof(cx)); memset(cy, 0xff, sizeof(cy));
    for (p = 1, flag = 1; flag; p++){
        flag = 0; for (cur = tail = 0, i = 0; i < nx; i ++) if (cx[i] == -1)
            open[++tail] = i, pred[i] = -1, src[i] = i;
        for (; cur <= tail; cur++){
            u = open[cur]; if (cx[src[u]] != -1) continue;
            for (v = 0; v < ny; v ++) if (g[u][v] && mk[v] != p){
                mk[v] = p; open[++tail] = cy[v]; if (open[tail] >= 0) { pred[open[tail]] = u; src[open[tail]] = src[u]; continue; }
                for (tail--, flag = 1, d = u, e = v; d != -1; t = cx[d], cx[d] = e, cy[e] = d, e = t, d = pred[d]);
                break;
            }
        }
    }
    for (i = 0; i < n; i++) res += (cx[i] != -1);
    return res;
}