ACM/ICPC 之 机器调度-匈牙利算法解最小点覆盖集(DFS)(POJ1325)

//匈牙利算法-DFS

//求最小点覆盖集 == 求最大匹配

//Time:0Ms  Memory:208K

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MAX 105

#define INF 0x3f3f3f3f

int n,m,k;

int gp[MAX][MAX];

bool sx[MAX],sy[MAX];    //访问数组

int cx[MAX],cy[MAX];    //匹配数组

int path(int u)

{

    sx[u] = true;

    for(int i = 1; i < m; i++)  //从模式1开始枚举

    {

        if(gp[u][i] && !sy[i]) {    //邻接且未访问

            sy[i] = true;

            if(!cy[i] || path(cy[i])){  //v未匹配 或 可从cy[v]出发找到一条增广路

                cx[u] = i;  cy[i] = u;

                return 1;   //回退中修改增广路匹配

            }

        }

    }

    return 0;

}

int getMaxMatch()

{

    int maxMatch = 0;

    memset(cx,0,sizeof(cx));

    memset(cy,0,sizeof(cy));

    for(int i = 1; i < n; i++)  //作业完成模式在0时不需重启-从模式1开始枚举

    {

        if(!cx[i]){ //模式0时

            memset(sx, false, sizeof(sx));

            memset(sy, false, sizeof(sy));

            maxMatch += path(i);

        }

    }

    return maxMatch;

}

int main()

{

    //freopen("in.txt", "r", stdin);

    while(scanf("%d", &n), n)

    {

        scanf("%d%d", &m, &k);

        memset(gp,0,sizeof(gp));

        for(int i = 0; i < k; i++)

        {

            int a,b,t;

            scanf("%d%d%d", &t,&a,&b);

            gp[a][b] = 1;

        }

        printf("%d\n", getMaxMatch());

    }

    return 0;

}