二部グラフにおいて最大マッチングを求める問題は、最大流で解くことができると聞きました。
しかし最大流を解くプログラムは理解できたのですがそれを二部グラフにおいて最大マッチングを求めるにはどのようにしたら良いのかいいのかわかりません。
まだまだ知識が浅くわかりづらいかもしれませんがよろしくお願いいたします。
以下が最大流のプログラムです。
java
1import java.util.*; 2public class MaxFlow{ 3 static class Edge{ 4 int to,cap,rev; 5 public Edge(int to,int cap,int rev){ 6 this.to = to; 7 this.cap = cap; 8 this.rev = rev; 9 } 10 public String toString(){ 11 return "#edge:["+to+","+cap+","+rev+"]"; 12 } 13 } 14 int MAX_V; 15 Vector<Vector<Edge>> graph; 16 boolean[] used; 17 public MaxFlow(int n){ 18 MAX_V = n; 19 graph = new Vector<Vector<Edge>>(); 20 for(int i=0; i<MAX_V; i++) graph.add(new Vector<Edge>()); 21 used = new boolean[MAX_V]; 22 } 23 void addEdge(int from,int to,int cap){ 24 graph.get(from).add(new Edge(to,cap,graph.get(to).size())); 25 graph.get(to).add(new Edge(from,0,graph.get(from).size()-1)); 26 } 27 int dfs(int v,int t,int f){ 28 if(v==t) return f; 29 used[v] = true; 30 for(int i=0; i<graph.get(v).size(); i++){ 31 Edge e = graph.get(v).get(i); 32 if(!used[e.to]&&e.cap>0){ 33 int d = dfs(e.to,t,Math.min(f,e.cap)); 34 if(d > 0){ 35 e.cap -= d; 36 graph.get(e.to).get(e.rev).cap += d; 37 return d; 38 } 39 } 40 } 41 return 0; 42 } 43 int solve(int s,int t){ 44 int flow = 0; 45 for(;;){ 46 for(int i=0; i<used.length; i++) used[i] = false; 47 int f = dfs(s,t,Integer.MAX_VALUE); 48 if(f==0) return flow; 49 flow += f; 50 } 51 } 52 public static void main(String[] args){ 53 Scanner sc = new Scanner(System.in); 54 int n = sc.nextInt(); 55 MaxFlow mf = new MaxFlow(n); 56 int m = sc.nextInt(); 57 for(int i=0; i<m; i++){ 58 int from = sc.nextInt(); 59 int to = sc.nextInt(); 60 int cap = sc.nextInt(); 61 mf.addEdge(from,to,cap); 62 } 63 int src = sc.nextInt(); 64 int dst = sc.nextInt(); 65 System.out.println(mf.solve(src,dst)); 66 } 67}
二部グラフは以下のようにデータでおきたいと考えています。
3 3 5
1
1
1
0 0
0 1
1 0
1 2
2 0
教えていただけたら嬉しく思います。
よろしくお願いいたします。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。