二分图最大匹配的 hopcroft-karp 算法

求二分图最大匹配的经典算法为匈牙利算法，时间复杂度为 O(nm)，还有一个 hopcroft-karp 算法，时间复杂度有些改进，为 O( sqrt(n)* m )。

hopcroft-karp 算法的精髓在于同时寻找多条增广路径，先用 BFS 求出一个层次图，类似求最大流算法中 Dinic 算法的层次图，然后在层次图中遍历，寻找增广路径，直到找不到为止。

 

代码实现(HDU2389):

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;

int const N= 3010;
int dist[N<<1], mx[N], my[N], m, n;
vector<int> map[N];

int que[N<<1], rear, tail;

int bfs(){
    rear= 0, tail= -1;
    for( int i= 1; i<= n; ++i ){
        if( mx[i]== -1 ) que[++tail]= i;
    }
    for( int i= 0; i<= n+ m; ++i ) dist[i]= 0;
    
    int flag= 0;
    while( rear<= tail ){
        int u= que[rear++];
        for( size_t i= 0; i< map[u].size(); ++i ){
            int v= map[u][i];
            if( dist[n+v]== 0 ){
                dist[n+v]= dist[u]+ 1;
                
                if( my[v]!= -1 ) {
                    dist[ my[v] ]= dist[n+ v]+ 1;
                    que[++tail]= my[v];
                }
                else flag= 1;
            }
        }
    }
    
    return flag;
}

int dfs( int u ){
    for( size_t i= 0; i< map[u].size(); ++i ){
        int v= map[u][i];
        
        if( dist[u]+ 1== dist[v+ n] ){
            int t= my[v];
            dist[v+n]= 0;
            if( t== -1 || dfs( t ) ){
                my[v]= u; mx[u]= v;
                return 1; }
        }
    }
    return 0;
}

int solve(){
    for( int i= 0; i<= n; ++i ) mx[i]= -1;
    for( int i= 0; i<= m; ++i ) my[i]= -1;
    
    int ans= 0;
    while( bfs() ){
        for( int i= 1; i<= n; ++i )
        if( mx[i]== -1 && dfs(i) ) ans++;
    }
    
    return ans;
}

int t, ux[N], uy[N], gx[N], gy[N], speed[N];

int inline isok( int x1, int y1, int x2, int y2, int s ){
    return sqrt( 1.0* (x1-x2)* (x1-x2)+ (y1-y2)* (y1-y2) )/ s<= 1.0* t;
}

void build(){
    scanf("%d",&t );
    scanf("%d",&n );
    for( int i= 1; i<= n; ++i )
    scanf("%d%d%d", gx+ i, gy+ i, speed+ i );
    
    scanf("%d",&m );
    for( int i= 1; i<= m; ++i )
    scanf("%d%d", ux+ i, uy+ i );
    
    for( int i= 1; i<= n; ++i )
    for( int j= 1; j<= m; ++j )
    if( isok( gx[i], gy[i], ux[j], uy[j], speed[i] ) )
    map[i].push_back( j );
}

int main(){
    int test;
    scanf("%d",&test );
    for( int ca= 1; ca<= test; ++ca ){
        build();
        printf("Scenario #%d:\n%d\n\n", ca, solve() );
        
        for( int i= 0; i<= n; ++i ) map[i].clear();
    }
    
    return 0;
}