问题 H: 棋盘游戏(二分图变式)

 题意：要求找到

不放车就无法达到最大数的点                     的个数

题解：1.以行列绘制二分图

           2.先算出最大二分匹配数

           3.依次遍历所有边

  删除该边，并计算二分匹配最大值

（若小于原最大值即为重要点），再恢复该边

以下为AC代码：

#include<string.h>
#include<iostream>
using namespace std;// 声明棋盘
int map[109][109] = { 0 };// 限制访问
int visit[109] = { 0 };// 右侧对象数组
int r[109] = { 0 };// 声明棋盘行列,棋子个数
int line = 0, row = 0, num = 0;// 二分匹配
bool find(int x);// 求最大匹配数
int max1();// 遍历删除并恢复所有边，求影响最大二分匹配的边
int max2();// 声明最大二分匹配数
int ans = 0;// 记录各边左右端点对应的下标
int k = 0;
int main()
{// 声明棋盘编号int n = 1;while (scanf("%d%d%d", &line, &row, &num) != EOF){memset(map, 0, sizeof(map));for (int i = 0; i < num; i++){int tl = 0, tr = 0;scanf("%d %d", &tl, &tr);map[tl][tr] = 1;}ans = max1();printf("Board %d have %d important blanks for %d chessmen.\n", n, max2(), max1());n++;}return 0;
}
// 二分匹配
bool find(int x)
{// 遍历右侧元素for (int i = 1; i <= row; i++){// 判断有无边,是否被访问if (map[x][i] && !visit[i]){visit[i] = 1;if (!r[i] || find(r[i])){r[i] = x;return 1;}}}return 0;
}
// 求最大匹配数
int max1()
{int ans1 = 0;memset(r, 0, sizeof(r));for (int i = 1; i <= line; i++){memset(visit, 0, sizeof(visit));if (find(i))ans1++;}return ans1;
}
// 遍历删除并恢复所有边，求影响最大二分匹配的边
int max2()
{int tans = 0, point = 0;for (int j = 1; j <= line; j++){for (int i = 1; i <= row; i++){if (map[j][i]){tans = 0;map[j][i] = 0;tans = max1();map[j][i] = 1;if (tans < ans) point++;}}}return point;
}