POJ - 1325 Machine Schedule 二分图 最小点覆盖

题目大意：有两个机器，A机器有n种工作模式，B机器有m种工作模式，刚开始两个机器都是0模式，如果要切换模式的话，机器就必须的重启
有k个任务，每个任务都可以交给A机器的i模式或者B机器的j模式完成，问要重启多少次机器才能完成任务

解题思路：两个机器的点分为两个点集，点集之间的关系就是任务了，要将所有任务都完成，就要将所有边都覆盖掉，所以就是求最小点覆盖了。
这里有一个点要注意，如果所有任务中都有一个0，那么机器就不用重启了，重启次数就为0了(因为刚开始都是0)

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int N = 110;
int n, m, k;
int vis[N], link[N];
bool flag;
vector<int> g[N];

void init() {

    for(int i = 1; i < n; i++)
        g[i].clear();

    int x, y, z;
    for(int i = 0; i < k; i++) {
        scanf("%d%d%d", &x, &y, &z);
        if(y * z == 0)
            continue;
        g[y].push_back(z);
    }
    memset(link, -1, sizeof(link));
}

bool dfs(int u) { 
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if(vis[v])
            continue;
        vis[v] = 1;
        if(link[v] == -1 || dfs(link[v])) {
            link[v] = u;
            return true;
        }
    }
    return false;
}

void hungary() {
    int ans = 0;
    for(int i = 1; i < n; i++) {
        memset(vis, 0, sizeof(vis));
        if(dfs(i))
            ans++;
    }
    printf("%d\n",ans);
}

int main() {
    while(scanf("%d", &n) != EOF && n) {
        scanf("%d%d", &m, &k);
        init();
        hungary();
    }
    return 0;
}