[UVa] 1194 Machine Schedule.cpp

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> edge[105];
int llink[105], rlink[105];
bool used[105];

bool dfs(int now)
{
    for (int nxt : edge[now]) {
        if (used[nxt]) continue;

        used[nxt] = true;
        if (rlink[nxt] == -1 || dfs(rlink[nxt]) == true) {
            llink[now] = nxt;
            rlink[nxt] = now;
            return true;
        }
    }
    return false;
}
int main()
{
    int n, m, k;
    while (scanf("%d", &n) && n) {
        for (auto &v : edge) v.clear();

        // Input
        scanf("%d %d", &m, &k);
        int i, x, y;
        for (int j = 0; j < k; ++j) {
            scanf("%d %d %d", &i, &x, &y);
            if (!x || !y) continue;         // mode 0直接忽略!
            edge[x].push_back(y);
        }
        // Bipartite
        int result = 0;
        fill(begin(llink), end(llink), -1);
        fill(begin(rlink), end(rlink), -1);

        for (int i = 0; i < n; ++i) {
            fill(begin(used), end(used), false);
            if (dfs(i) == true) ++result;
        }
        // Output
        printf("%d\n", result);
    }
}