HR Bike Racers ( Binary Search + Maximum Matching )

https://www.hackerrank.com/challenges/bike-racers
參考了這篇：用于二分图匹配的匈牙利算法 | Comzyh的博客
第一次寫二分圖最大匹配，原來沒有想像中那麼難。我想二分圖最大匹配基本上可以想成是求婚問題，一群男士和一群女士有一些關聯，這些關聯可以用邊描述（要嘛相互能接受，要嘛相互不能接受），這時候要替他們匹配，使得最多組相互能接受的男女配對產生（當然不允許同一個人存在於多組的情形）。
為什麼是說求婚問題呢，想像是匹配的一邊是男生，另一邊是女生，且規定男生要主動追求女生。按編號每一個男生挑選理想的女生，如果該女生還沒有追求者，就形成配對，結束。否則試著踢開該女生的男士，接著讓被踢開的男士遞迴著找當前有沒有可配對的女生，有的話就各自配對，返回，如此就又多一對了。每一個男士挑選完後，將是最大匹配。
這個問題只要會最大匹配就很顯然了，二分時間，構圖判斷最大匹配是否滿足 K。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair< int, int > pii;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef vector< pii > vpii;
typedef vector< char > vch;

const int MOD7 = 1e9 + 7;
const int INF = 0x3f3f3f3f;

// #define MULTIPLE_CASES

struct Hungarian{
    vvi G;
    vi bf;
    int girl_size;
    vi vis;

    Hungarian( const vvi &_G, const int gs ): G( _G ), girl_size( gs ){
        bf.resize( girl_size );
        vis.resize( girl_size );
        fill( bf.begin(), bf.end(), -1 );
    }

    bool foundMate( int u, const vvi &G ){
        for( int v : G[ u ] ){ // u: boy, v: girl
            if( vis[ v ] ) continue;
            vis[ v ] = 1;
            if( bf[ v ] == -1 || foundMate( bf[ v ], G ) )
                return ( bf[ v ] = u ) or true;
        }
        return false;
    }

    int maxMatch(){
        int res = 0;
        for( int i = 0; i < G.size(); ++i ){
            fill( vis.begin(), vis.end(), 0 );
            if( foundMate( i, G ) ) ++res;
        }
        return res;
    }
};

ll eulerDisSqr( const pii &p1, const pii &p2 ){
    ll dx = p1.first - p2.first;
    ll dy = p1.second - p2.second;
    return dx * dx + dy * dy;
}

bool ok( ll x, int gol, const vpii &player_pos, const vpii &bike_pos ){
    vvi G( player_pos.size() );
    for( int i = 0; i < player_pos.size(); ++i )
        for( int j = 0; j < bike_pos.size(); ++j )
            if( eulerDisSqr( player_pos[ i ], bike_pos[ j ] ) <= x )
                G[ i ].push_back( j );
    Hungarian hung( G, bike_pos.size() );
    return hung.maxMatch() >= gol;
}

void solve(){
    int N, M, K; cin >> N >> M >> K;
    vpii player_pos( N ), bike_pos( M );
    for( int i = 0; i < N; ++i )
        cin >> player_pos[ i ].first >> player_pos[ i ].second;
    for( int i = 0; i < M; ++i )
        cin >> bike_pos[ i ].first >> bike_pos[ i ].second;
    ll lb = 0, rb = 1e16;
    ll ans = -1;
    while( lb <= rb ){
        ll mid = ( lb + rb ) / 2;
        if( ok( mid, K, player_pos, bike_pos ) ) ans = mid, rb = mid - 1;
        else lb = mid + 1;
    }
    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio( false );
    cin.tie( 0 );
    cout.tie( 0 );

    #ifdef MULTIPLE_CASES
        int T; cin >> T; while( T-- ) solve();
    #endif

    #ifndef MULTIPLE_CASES
        solve();
    #endif

    return 0;
}