HDU 1150 Machine Schedule（最小点覆盖问题）
/*题意：A机器n种工作模式，B机器m种工作模式，共有k个任务。（i,x,y）代表：任务i可由A机器x模式或者B机器y模式完成。任务顺序可以随便改动，如果A或者B机器需要更换模式，则需要重启机器。求完成工作，需要最少启动机器次数。解题思路：画出二分图，易知该问题为最小点覆盖问题，最小顶点覆盖 = 最大匹配数*/#include <iostream>using namespace std;const int nMax = 105;int n, m, k;int map[nMax][nMax];int link[nMax];int useif[nMax];bool can(int t){for(int i = 1; i <= m; ++ i){if(!useif[i] && map[t][i]){useif[i] = 1;if(link[i] == -1 || can(link[i])){link[i] = t;return 1;}}}return 0;}int main(){//freopen("f://data.in", "r", stdin);while(1){memset(map, 0, sizeof(map));memset(link, -1, sizeof(link));int num = 0;scanf("%d", &n);if(!n) break;scanf("%d%d", &m, &k);for(int i = 0; i < k; ++ i){int a, b, c;scanf("%d %d %d", &a, &b, &c);map[b][c] = 1;}for(int i = 1; i <= n; ++ i){memset(useif, 0, sizeof(useif));if(can(i)) ++ num;}printf("%d\n", num);}return 0;}