二部グラフのマッチング

Question

二部グラフにおいて最大マッチングを求める問題は、最大流で解くことができると聞きました。
しかし最大流を解くプログラムは理解できたのですがそれを二部グラフにおいて最大マッチングを求めるにはどのようにしたら良いのかいいのかわかりません。
まだまだ知識が浅くわかりづらいかもしれませんがよろしくお願いいたします。
以下が最大流のプログラムです。

import java.util.*;
public class MaxFlow{
    static class Edge{
	int to,cap,rev;
	public Edge(int to,int cap,int rev){
	    this.to = to;
	    this.cap = cap;
	    this.rev = rev;
	}
	public String toString(){
	    return "#edge:["+to+","+cap+","+rev+"]";
	}
    }
    int MAX_V;
    Vector<Vector<Edge>> graph;
    boolean[] used;
    public MaxFlow(int n){
	MAX_V = n;
	graph = new Vector<Vector<Edge>>();
	for(int i=0; i<MAX_V; i++) graph.add(new Vector<Edge>());
	used = new boolean[MAX_V];
    }
    void addEdge(int from,int to,int cap){
	graph.get(from).add(new Edge(to,cap,graph.get(to).size()));
	graph.get(to).add(new Edge(from,0,graph.get(from).size()-1));
    }
    int dfs(int v,int t,int f){
	if(v==t) return f;
	used[v] = true;
	for(int i=0; i<graph.get(v).size(); i++){
	    Edge e = graph.get(v).get(i);
	    if(!used[e.to]&&e.cap>0){
		int d = dfs(e.to,t,Math.min(f,e.cap));
		if(d > 0){
		    e.cap -= d;
		    graph.get(e.to).get(e.rev).cap += d;
		    return d;
		}
	    }
	}
	return 0;
    }
    int solve(int s,int t){
	int flow = 0;
	for(;;){
	    for(int i=0; i<used.length; i++) used[i] = false;
	    int f = dfs(s,t,Integer.MAX_VALUE);
	    if(f==0) return flow;
	    flow += f;
	}
    }
    public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	MaxFlow mf = new MaxFlow(n);
	int m = sc.nextInt();
	for(int i=0; i<m; i++){
	    int from = sc.nextInt();
	    int to = sc.nextInt();
	    int cap = sc.nextInt();
	    mf.addEdge(from,to,cap);
	}
	int src = sc.nextInt();
	int dst = sc.nextInt();
	System.out.println(mf.solve(src,dst));
    }
}

二部グラフは以下のようにデータでおきたいと考えています。

3 3 5
1
1
1
0 0
0 1
1 0
1 2
2 0

教えていただけたら嬉しく思います。
よろしくお願いいたします。

Answer 1

最大二部マッチング問題を最大流問題に帰着する説明へのリンクです。

二部マッチング（Jeff Erickson 著 Algorithms の翻訳）
最大二部マッチング問題を最大流問題に帰着する

マッチングの入力を最大流の入力に変換して解くので、プログラムの変更は（最大流問題を解けているなら）入力の変換で十分だと思います。