机器任务

AcWing-376-机器任务

分析

见《进阶指南》第434页。

实现

#include <iostream>
#include <cstring>
using namespace std;

const int N = 210, M = 2010;
struct edge {
    int to, next;
};
edge e[M];
int idx, head[N];
int n, m, k;
bool mark[N];
int match[N];

void add_edge (int u, int v) {
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
bool dfs (int cur) {
    for (int i = head[cur]; i != -1; i = e[i].next) {
        int to = e[i].to;
        if (mark[to] == true) continue;
        mark[to] = true;
        if (match[to] == 0 || dfs(match[to]) == true) {
            match[to] = cur;
            return true;
        }
    }
    return false;
}

int main () {
    while (cin >> n >> m >> k && n) {
        idx = 0;
        memset(head, -1, sizeof(head));
        memset(match, 0, sizeof(match));
        for (int i = 0, a, b; i < k; ++ i) {
            cin >> i >> a >> b;
            if (a == 0 || b == 0) continue;
            add_edge(a, n + b);
            add_edge(n + b, a);
        }

        int res = 0;
        for (int i = 1; i <= n - 1; ++ i) {
            memset(mark, 0, sizeof(mark));
            if (dfs(i) == true) ++ res;
        }
        cout << res << endl;
    }
    return 0;
}