`
duoerbasilu
  • 浏览: 1474459 次
文章分类
社区版块
存档分类
最新评论

HDU 1150 Machine Schedule(最小点覆盖问题)

 
阅读更多
/*
题意:
A机器n种工作模式,B机器m种工作模式,共有k个任务。(i,x,y)代表:任务i可由A机器x模式或者B机器y模式完成。任务顺序可以随便改动,如果A或者B机器需要更换模式,则需要重启机器。求完成工作,需要最少启动机器次数。

解题思路:
画出二分图,易知该问题为最小点覆盖问题,最小顶点覆盖 = 最大匹配数

证明参见Konig定理:
http://www.cppblog.com/abilitytao/archive/2009/09/02/95147.html
http://www.matrix67.com/blog/archives/116
*/

#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;
}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics