//Sample Input
3 3 4
1 2
1 3
2 1
2 2
3 3 4
1 2
1 3
2 1
3 2//Sample Output
Board 1 have 0 important blanks for 2 chessmen.
Board 2 have 3 important blanks for 3 chessmen.

题意：如图。

算法：Hungary

问题：注意数组大小……debug了好久

//以后板子题样例过了但wa了，重点看看是不是数组开小了或者memset位置不对。

思路： 位置的横纵坐标构成二部图，求能放几个棋子就是求最大匹配，枚举尝试去除某一个位置，看最大匹配数是否减少，如果减少，这个位置就是“重要点”。

代码：ac

#include<bits/stdc++.h>
using namespace std;
int con[110][110];
int vis[110];
int link[110];
int n, m;
int find(int x)
{for (int i = 1; i <= m; i++){if (vis[i] == 0 && con[x][i] == 1){vis[i] = 1;if (link[i] == -1 || find(link[i])){link[i] = x;return 1;}}}return 0;
}
int hungary()
{int res = 0;memset(link, -1, sizeof(link));for (int x = 1; x <= n; x++) {memset(vis, 0, sizeof(vis));if (find(x))res++;}return res;
}
int x[10010], y[10010];/*注意这里数组大小是k的范围*/
int main()
{int k;int count = 1;while (scanf("%d%d%d", &n, &m, &k) == 3) {memset(con, 0, sizeof(con));for (int i = 1; i <= k; i++) {scanf("%d%d", &x[i], &y[i]);con[x[i]][y[i]] = 1;}int sum = hungary();int cnt = 0;for (int i = 1; i <= k; i++) {con[x[i]][y[i]] = 0;if (hungary() < sum)cnt++;con[x[i]][y[i]] = 1;}printf("Board %d have %d important blanks for %d chessmen.\n", count++, cnt, sum);}return 0;
}