poj 1325 Machine Schedule（最小顶点覆盖+最大匹配）

http://poj.org/problem?id=1325

题意：有AB两台机器和k个任务，机器A有n种模式，机器B有m种模式，初始均工作在模式0，每个任务都可以由机器A的一种模式或机器B的一种模式完成，每次切换模式都需要代价1，要求用最小的代价完成所有任务。

思路：

A的n种模式和B的m种模式自成一个集合，显然是一个二分图的模型。令X= {机器A的模式}，Y={机器B的模式}， E= {（i,j）| job K 可由机器A的模式i或机器B的模式j完成}，这样构造了一个二分图G= {X,Y,E}.

本题是一类最小顶点覆盖的问题，将机器A和机器B的某个工作模式看做顶点，某个任务看做一条边，那么问题就转化为是否存在一个最小规模的点集，使得所有的边都至少和该点集中的一个顶点关联。

而二分图的最小顶点覆盖问题与最大匹配问题是等价的。由于本题机器AB初始都工作在mode_0,那么被机器AB的mode_0模式覆盖的顶点可以不需要额外考虑。

#include <stdio.h>
#include <string.h>
const int maxn = 110;

int map[maxn][maxn];	//邻接矩阵存二分图
int chk[maxn];			//记录点是否被扫描过
int match[maxn];		//存储匹配方案
int n,m,k;

bool dfs(int p)
{
	for(int i = 0; i < m; i++)
	{
		if(map[p][i] && !chk[i])//找到p的一个对应点且该点没有被检查过,(检查即尝试过更改i的匹配)
		{
			chk[i] = 1;
			if(match[i] == -1 || dfs(match[i]))//如果i未在匹配中或者i在匹配中但是从与i相邻的节点出发可以有增广路
			{
				match[i] = p;//与i匹配的点更改为p
				return true;//多了一条匹配边
			}
		}
	}
	return false;
}

int main()
{
	while(~scanf("%d",&n))
	{
		if(n == 0) break;
		scanf("%d %d",&m,&k);
		memset(map,0,sizeof(map));
		memset(match,-1,sizeof(match));

		int x,y,z;
		for(int i = 0; i < k; i++)
		{
			scanf("%d %d %d",&x,&y,&z);
			if(y*z != 0)
				map[y][z] = 1;
		}
		
		int res = 0;

		for(int i = 0; i < n; i++)		//对n个点依次进行增广
		{
			memset(chk,0,sizeof(chk));	//一次增广中对chk初始化
			if(dfs(i)) res += 1;		//增广成功，表示i点找到了一个匹配，多了一条匹配边
		}
		printf("%d\n",res);
	}
	return 0;
}