[図論]二分図マッチング(ハンガリーアルゴリズム)

紹介部分はウィキペディアに転載されています.
ハンガリーアルゴリズムは多くの線形タスク割り当て問題を解決するためのアルゴリズムの一つであり、二分図の最大整合問題を解決するための古典的なアルゴリズムであり、多項式時間内に問題を解決することができ、米国の数学者Harold Kuhnが1955年に提案した.このアルゴリズムがハンガリーアルゴリズムと呼ばれているのは,アルゴリズムの大部分が以前のハンガリー数学者DénesKに基づいているからである.őnigとJenő Egerváryの仕事の上で作成された.質問の概要:
G=(V,E)を無方向図とする.頂点セットVが互いに交差しない2つのサブセットV 1,V 2の和に分割され、図中の各エッジに付随する2つの頂点は、この2つの異なるサブセットに属する.図Gを二分図と呼ぶ.二分図は、G=(V 1,V 2,E)とも記すことができる.二分図Gが与えられ、Gのサブ図Mにおいて、Mのエッジセット{E}のいずれのエッジも同じ頂点に依存しない場合、Mは一致すると称される.このようなサブセットのエッジ数が最大のサブセットを選択することを図の最大マッチング問題(maximal matching problem)と呼び、図のすべての頂点があるマッチングの1つのエッジに関連付けられている場合、このマッチングを完全マッチングと呼び、完全マッチングとも呼ばれる.アルゴリズムの説明:
最大マッチングを求める明らかなアルゴリズムの1つは、まずすべてのマッチングを見つけてから、マッチング数を最も多く保持することです.しかし,このアルゴリズムの時間複雑度は辺数の指数関数である.従って,より効率的なアルゴリズムを求める必要がある.次に,拡張路を用いて最大マッチングを求める方法(ハンガリーアルゴリズムと呼ばれ,数学者Harold Kuhnが1955年に提案した)を紹介する.拡張路の定義(拡張レールまたはインターリーブレールとも呼ばれる):Pが図Gの2つの未整合頂点を連通する経路であり、Mに属するエッジとMに属さないエッジ(すなわち、一致したエッジと一致するエッジ)がP上で交互に現れる場合、PはMに対する拡張経路と呼ばれる.(Mは1つのマッチングである)拡張路の定義から,1−Pの経路長は必ず奇数であり,第1のエッジと最後のエッジはいずれもMに属さないという3つの結論が得られる.2−MおよびPを異種化または操作(異種化を除く)することによって、より大きなマッチングM’を得ることができる.3−MはGの最大整合であり、Mの広がり経路が存在しない場合のみである.アルゴリズムプロファイル:(1)Mを空にする(2)拡張パスPを見つけ,M(3)の代わりに異或操作によりよりより大きなマッチングM’を得る(2)拡張パスが見つからないまで時間空間複雑度:時間複雑度隣接マトリクス:最悪O(n^3)隣接テーブル:O(mn)空間複雑度隣接マトリクス:O(n^2)隣接テーブル:O(m+n)
比較的直感的にマッチングプロセスを理解するには、ブログを参照してください.http://blog.csdn.net/dark_scope/article/details/8880547
個人メモ:二分図では、左の頂点個数をun、右の頂点個数をvnとし、g[i][j]は左の定点iと右の頂点jの間に辺がつながっていることを示し、右のi番目の頂点に一致するのは左のどの頂点であるかをlinked[i]で表す.まず左の点を巡り、左の頂点ごとに右の頂点にマッチします.実行可能な一致が見つかった場合、右の頂点が一致したとマークされます.この左の点の一致プロセスはこれで終わり、次の左の頂点を巡ります.左の頂点にエッジがある右の頂点が一致した場合、それに一致する左の頂点がXであると仮定します.では、Xを再マッチングして、現在マッチングが必要な左のポイントに右の頂点を譲ることができるかどうかを確認します.ちょっと回ります.例えば、左側の頂点aと右側のc、dに辺があり、左側の頂点bと右側の頂点cに辺があり、最初に一致したのはa、aとcで一致し、aの一致が終わった後、bに一致し、bに辺がつながっている右側の頂点cが一致していることを発見し、それに一致した頂点は左の頂点aである場合、aを再一致させ、aが別の頂点に一致するかどうかを見ることができます.cという頂点を「空席を空ける」と,aもdと一致し,bとcを一致させるために空を空けることができることが分かった.これがハンガリーのアルゴリズムが重要な場所です.
テンプレート:hdu 2063

/*
                
          ,g[i][j]
maxn          ,un       ，vn       
linked[i]      i           
*/

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn=502;
int un,vn;//     ，     
int g[maxn][maxn];//        
int linked[maxn];//             
bool vis[maxn];

bool dfs(int u)
{
    for(int v=1;v<=vn;v++)//      
    {
        if(g[u][v]&&!vis[v])
        {
            vis[v]=1;
            if(!linked[v]||dfs(linked[v]))//          ，                              “    ”        u
            {
                linked[v]=u;
                return true;
            }
        }
    }
    return false;
}

int hungary()
{
    int ans=0;
    memset(linked,0,sizeof(linked));
    for(int u=1;u<=un;u++)//      ，            
    {
        memset(vis,0,sizeof(vis));
        if(dfs(u))//  u     ,        ,ans++
            ans++;
    }
    return ans;
}

int k,m,n;//m              ,n              
int main()
{
    while(scanf("%d",&k)!=EOF&&k)
    {
        scanf("%d%d",&m,&n);
        un=m;vn=n;
        memset(g,0,sizeof(g));
        int u,v;
        for(int i=1;i<=k;i++)
        {
            scanf("%d%d",&u,&v);//u v  
            g[u][v]=1;
        }
        printf("%d
",hungary());
    }
    return 0;
}