hdu1281 棋盘游戏（枚举 + 二分图最大婚配）

hdu1281 棋盘游戏（枚举 + 二分图最大匹配）

/*
题解：枚举 + 二分图最大匹配
棋盘行和列分别作AB集合，如果可以放旗子，则Ai 与 Bi连一条边，令map[i][j] = 1。同行与同列至多存在一个棋子，等于同一个点只能被一条边覆盖，于是棋盘中可以放最多棋子问题便转换成寻找最大匹配问题。由于本题中要求找出存在多少关键点，枚举每一个map[i][j] = 1的点，如果将map[i][j] = 0后，得到最大匹配值小于原来最大匹配值，则该节点为关键点。
*/

#include <iostream>
using namespace std;

const int nMax = 105;
int link[nMax];
int useif[nMax];
int map[nMax][nMax];
int n, m, k;

int getPath(int t)
{
	for(int i = 0; i < m; ++ i)
	{
		if(!useif[i] && map[t][i])
		{
			useif[i] = 1;
			if(link[i] == -1 || getPath(link[i]))
			{
				link[i] = t;
				return 1;
			}
		}
	}
	return 0;
}

int getNum()
{
	int ans = 0;
	memset(link, -1, sizeof(link));
	for(int i = 0; i < n; ++ i)
	{
		memset(useif, 0, sizeof(useif));
		ans += getPath(i);
	}
	return ans;
}

int main()
{
	//freopen("f://data.in", "r", stdin);
	int cas = 0;
	while(scanf("%d %d %d", &n, &m, &k) != EOF)
	{
		memset(map, 0, sizeof(map));
		while(k --)
		{
			int a, b;
			scanf("%d %d", &a, &b);
			-- a;
			-- b;
			map[a][b] = 1;
		}
		int num = getNum();
		int ans = 0;
		for(int i = 0; i < n; ++ i)
			for(int j = 0; j < m; ++ j)
			{
				if(map[i][j])
				{
					map[i][j] = 0;
					if(getNum() < num)
						ans ++;
					map[i][j] = 1;
				}
			}
		printf("Board %d have %d important blanks for %d chessmen.\n", ++cas, ans, num);
	}
	return 0;
}