HDU 1150 Machine Schedule(最小点覆盖有关问题)
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; }