質問編集履歴

2 aka1220 score 10 2018/01/20 11:08 投稿

二部グラフのマッチング

二部グラフにおいて最大マッチングを求める問題は、最大流で解くことができると聞きました。

しかし最大流を解くプログラムは理解できたのですがそれを二部グラフにおいて最大マッチングを求めるにはどのようにしたら良いのかいいのかわかりません。

まだまだ知識が浅くわかりづらいかもしれませんがよろしくお願いいたします。

以下が最大流のプログラムです。

```java

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

0 0

0 1

1 0

1 2

2 0

教えていただけたら嬉しく思います。

よろしくお願いいたします。

Java

18039 questions

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

625 questions

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

1 aka1220 score 10 2018/01/20 11:08 投稿