Hungarian Algoritim Template.

For Bipartite Graph..

We Named left Node by 0,1,2,3,4,5...
And the Right Node's names are also 0,1,2,3,4,5...
For each time we call dfs(), we always stand on the left side, to watch the right side.

Template

#include <iostream>
using namespace std;

const int MAXN=100;
const int MAXM=MAXN*MAXN;
struct Edge{
    int to;//to : rightNode
    Edge *next;
}g[MAXM],*head[MAXN];// head[leftIdx]
int eptr=0,n; // n: number of leftNode.
void addedge(int a, int b){
    g[eptr].to=b; g[eptr].next=head[a]; head[a]=&g[eptr++];
}

bool visited[MAXN]; //rightNode;
int path[MAXN]; // path[rightNode]=leftNode.
// I always stand on the left side to watch the right side.
// Each time we call dfs(), we try to shoot a pair from the left node 'p'.
bool dfs(int p) {//p:leftNode. e->to:rightNode.
    for (Edge *e=head[p]; e; e=e->next) 
        if (!visited[e->to]) {
            visited[e->to]=1;
            if (path[e->to]==-1 || dfs(path[e->to])) {
                path[e->to]=p;
                return true;
            }
    }
    return false;
}

int main() {
    //Make graph here..
    addedge(...);
    //Hungarian begin..
    memset(path,0xff,sizeof(path)); //Init match result.
    for (int i=0; i<n; i++) { //i: leftNode index.
        memset(visited, 0, sizeof(visited));
        if (!dfs(i)) {
            cout<<"Failure. Lose perfect match."<<endl;
            cout<<"Cannot find a pair for leftnode "<<i<<endl;
        }
    }
    cout<<"Finish to pair."<<endl;
    return 0;
}