二部グラフの最大マッチング

目的

二部グラフの最大マッチング数をFord-Fulkersonのアルゴリズムによって求めます。

使い方

int bipartiteMatching(ArrayList[] g, int L)
二部グラフg(隣接リスト表現)の最大マッチング数をreturnします。
0,1,..,L-1が左側の頂点(湧き出し側)、L,L+1,...,n-1が左側の頂点(吸い込み側の頂点)。
ただしnは頂点数。

ソースコード


boolean augment(ArrayList<Integer>[] g, int u, Integer[] matchTo, Boolean[] visited) {
    if (u < 0)
	return true;
    for (int v : g[u]) {
	if (!visited[v]) {
	    visited[v] = true;
	    if (augment(g, matchTo[v], matchTo, visited)) {
		matchTo[u] = v;
		matchTo[v] = u;
		return true;
	    }
	}
    }
    return false;
}

int bipartiteMatching(ArrayList<Integer>[] g, int L) {
    final int n = g.length;
    Integer[] matchTo = new Integer[n];
    Arrays.fill(matchTo, -1);
    matching = new ArrayList<>();
    int match = 0;

    for (int i = 0; i < L; i++) {
	Boolean[] visited = new Boolean[n];
	Arrays.fill(visited, false);
	if (augment(g, i, matchTo, visited))
	    match++;
    }
    for (int i = 0; i < L; i++) {
	if (matchTo[i] > 0)
	    matching.add(new Edge(i, matchTo[i]));
    }

    return match;
}

ArrayList<Edge> matching;

class Edge {
    int a;
    int b;

    Edge(int a, int b) {
	this.a = a;
	this.b = b;
    }
}

Verified

yukicoder No.421 しろくろチョコレート