匈牙利算法demo

本文的代码和思想都是参考自: https://blog.csdn.net/dark_scope/article/details/8880547。该文章对匈牙利算法的思想讲解的非常简单易懂，但是代码给得不是很完整，特此整理一下，给需要的人。

/*
*
* Reference: https://blog.csdn.net/dark_scope/article/details/8880547
*/

#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;

bool line[4][4]={{true, true, false, false}, {false, true, true, false}, {true, true, false, false}, {false, false, true, false}};
bool *used;
int *girl;
const int m = 4;

bool find(int x)
{
    for(int j=0; j<m; j++)
    {    
        if (line[x][j]==true && used[j]==false)      
        {
            used[j]=1;
            if (girl[j] == -1 || find(girl[j])) 
            { 
                girl[j]=x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    used = new bool[4]{false, false, false, false};
    girl = new int[4]{-1,-1,-1,-1};
    for(int i = 0; i < 4; i++)
    {
        memset(used, 0, 4);
        find(i);
    }

    for(int i = 0; i < 4; i++)
    {
        fprintf(stdout, "girl: %d <----> boy: %d
", i,  girl[i]);
    }
    delete []girl;
    delete []used;
    return 0;
}

/**terminal****

g++ hungarian.cpp -std=c++11 -o hungarian

./hungarian 

girl: 0 <----> boy: 2
girl: 1 <----> boy: 0
girl: 2 <----> boy: 1
girl: 3 <----> boy: -1

*/