advanced algorithms summer 2012

hk.cpp

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <iostream>

//#define HK_DEBUG

using namespace std;

#define VI vector<int>
#define VS vector<string>
#define MII map<int, int>
#define MSI map<string, int>
#define MIS map<int, string>
#define MSS map<string, string>

#define IT(T) T::iterator
#define MIII IT(MII)
#define MSII IT(MSI)
#define MISI IT(MIS)
#define MSSI IT(MSS)

#define HK_INF 300000
#define MAX_SIZE 100100

VI g[MAX_SIZE];
int pu[MAX_SIZE], pv[MAX_SIZE], dist[MAX_SIZE];
int p, q, n, m;
int bq[MAX_SIZE];

bool bfs(){
    int l = 0, r = 0;
    for(int v = 1; v <= p; v++){
        if(pu[v]){
            dist[v] = HK_INF;
        }
        else{
            dist[v] = 0;
            bq[r++] = v;
        }
    }

    dist[0] = HK_INF;
    while(l != r){
        int v = bq[l++];
        for(int i = 0; i < g[v].size(); i++){
            int w = pv[g[v][i]];
            if(dist[w] == HK_INF){
                dist[w] = dist[v] + 1;
                bq[r++] = w;
            }
        }
    }
    return dist[0] != HK_INF;
}

bool dfs(int v){
    if(!v)
        return true;

    for(int i = 0; i < g[v].size(); i++){
        int u = g[v][i];
        int w = pv[u];
        if(dist[w] == dist[v] + 1 && dfs(w)){
            pv[u] = v;
            pu[v] = u;
            return true;
        }
    }

    dist[v] = HK_INF;
    return false;
}

int main(){
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    cin >> p >> q >> m;
    n = p + q;
    for(int i = 0; i < m; i++){
        int v, u;
        cin >> v >> u;
        g[v].push_back(u);
//        g[v].push_back(u);
    }

    int cnt = 0;
    while(bfs()){
        for(int v = 1; v <= p; v++){
            if(!pu[v] && dfs(v)){
                cnt++;
#ifdef HK_DEBUG
                cout << "Your matching is: \n";
                for(int i = 1; i <= p; i++){
                    if(pu[i])
                        cout << i << " " << pu[i] << endl;
                }
#endif
            }
        }
    }
    cout << cnt << endl;

#ifndef DEBUG
    for(int i = 1; i <= p; i++){
        if(pu[i])
            cout << i << " " << pu[i] << endl;
    }
#endif
    return 0;
}