ハンガリーのアルゴリズムの改善したキューの最適化は極めて広いパスセットを探す--Hopcroft-Karpアルゴリズム【記録】

アルゴリズムの解:ハンガリーのアルゴリズムと解決した問題は、時間の複雑さを最適化したにすぎない.
アルゴリズム解析:sqrt(n)回を広げ,毎回辺数m,時間複雑度−O(sqrt(n)*mを遍歴する必要がある.
アルゴリズムの実装:
1,BFSは交差しない複数の拡張パスを探し,極大拡張パスセットを見つける.この過程で配列dx[],dy[]を設定してXセット,Yセットの階層図を作成することは,メンテナンス距離ラベルとして理解できる.
(不適切かもしれませんが、この点は最大ストリームDinicアルゴリズムのBFSと拡張路を探していますが、ここでは複数を探しています).
2,それから原版ハンガリーアルゴリズムのマッチング過程であり,階層図の判定が多かったにすぎない.
3,ずっとBFSは極大な拡幅のパスのセットを探して、もし拡幅の道が存在しないならば、飛び出して、アルゴリズムは終わります.
最大BFS探索sqrt(n)回で最大整合が得られることを証明できる.
コード:

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAXN 5000+10
using namespace std;
int mx[MAXN], my[MAXN];//  X Y       
int dx[MAXN], dy[MAXN];//      
bool used[MAXN];//      
vector<int> G[MAXN];//     
int n, m;//     
int numx, numy;//  X      Y     
int DFS(int u)//               
{
    for(int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        if(!used[v] && dy[v] == dx[u] + 1)
        {
            used[v] = true;
            if(my[v] == -1 || DFS(my[v]))
            {
                my[v] = u;
                mx[u] = v;
                return 1;
            }
        }
    }
    return 0;
}
void HK_match()
{
    memset(mx, -1, sizeof(mx));
    memset(my, -1, sizeof(my));
    int ans = 0;
    while(1)
    {
        bool flag = false;//           
        memset(dx, 0, sizeof(dx));
        memset(dy, 0, sizeof(dy));
        queue<int> Q;
        for(int i = 1; i <= numx; i++)
            if(mx[i] == -1) Q.push(i);
        while(!Q.empty())//     
        {
            int u = Q.front(); Q.pop();
            for(int i = 0; i < G[u].size(); i++)
            {
                int v = G[u][i];
                if(!dy[v])
                {
                    dy[v] = dx[u] + 1;//    Dinic         
                    if(my[v] == -1)//           
                    flag = true;
                    else
                    {
                        dx[my[v]] = dx[u] + 1;
                        Q.push(my[v]);
                    }
                }
            }
        }
        if(!flag)//      
            break;
        memset(used, false, sizeof(used));
        for(int i = 1; i <= numx; i++)
            if(mx[i] == -1)//           
                ans += DFS(i);
    }
    printf("%d
", ans);// X、Y       ， numx = numy = n，     2。
}
int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        getMap();//    G  
        HK_match();//HK  
    }
    return 0;
}