質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

91.03%

  • Java

    12108questions

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

  • アルゴリズム

    342questions

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

二部グラフのマッチング

受付中

回答 0

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 130

aka1220

score 6

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

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

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

まだ回答がついていません

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 91.03%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • Java

    12108questions

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

  • アルゴリズム

    342questions

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