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