棋盘游戏
题意
小希和Gardon在玩一个游戏：对一个N*M的棋盘，在格子里放尽量多的一些国际象棋里面的“车”，并且使得他们不能互相攻击，这当然很简单，但是Gardon限制了只有某些格子才可以放，小希还是很轻松的解决了这个问题（见下图）注意不能放车的地方不影响车的互相攻击。
所以现在Gardon想让小希来解决一个更难的问题，在保证尽量多的“车”的前提下，棋盘里有些格子是可以避开的，也就是说，不在这些格子上放车，也可以保证尽量多的“车”被放下。但是某些格子若不放子，就无法保证放尽量多的“车”，这样的格子被称做重要点。Gardon想让小希算出有多少个这样的重要点，你能解决这个问题么？
Input
输入包含多组数据， 第一行有三个数N、M、K(1<N,M<=100 1<K<=N*M)，表示了棋盘的高、宽，以及可以放“车”的格子数目。接下来的K行描述了所有格子的信息：每行两个数X和Y，表示了这个格子在棋盘中的位置。
Output
对输入的每组数据，按照如下格式输出： Board T have C important blanks for L chessmen.
Sample Input
1
2
3
4
5
6
7
8
9
10
3 3 4
1 2
1 3
2 1
2 2
3 3 4
1 2
1 3
2 1
3 2
Sample Output
1
2
Board 1 have 0 important blanks for 2 chessmen.
Board 2 have 3 important blanks for 3 chessmen.
思路
经过之前的题(HDU1045)的思路,这个题的建图肯定是缩点.
但是区别于上个题的是,这个车在一行内只能放一个,也就是一行只能缩成一个点.列也是同理.所以这个题的图显而易见,就是X部为行,Y部为列, u到v有边当且仅当mp[i][j]上可以放一个棋子.
那么问题来了,怎么求关键点呢.
观察这个题的数据范围,我们发现只要暴力求就可以了.匈牙利算法的复杂度是O(n*m),枚举每个在匹配中的点删掉再执行一遍算法就是O(n^2*m),n取100,m取1e4的话,是可行的.又考虑到很难跑到上限,所以是可以通过此题的.
当然,显然这题用邻接矩阵会很好做,用邻接表反而麻烦了.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
#define ll long long
#define maxn 1010
#define maxm int(1e6) + 100
using namespace std;
bool mp[maxn][maxn];
int n, m, k;
int used[maxn], vis[maxn];
bool Find(int u, int dfn) {
for (int i = 1; i <= m; ++i) {
if (mp[u][i]) {
if (vis[i] != dfn) {
vis[i] = dfn;
if (!used[i] || Find(used[i], dfn)) {
used[i] = u;
return true;
}
}
}
}
return false;
}
int match() {
int ans = 0;
for (int i = 1; i <= n; ++i) {
vis[i] = 0;
used[i] = 0;
}
for (int i = 1; i <= n; ++i) {
if (Find(i, i)) {
++ans;
}
}
return ans;
}
int main() {
int cnt = 0;
while (scanf("%d%d%d", &n, &m, &k) != EOF) {
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
mp[i][j] = 0;
}
}
for (int i = 0; i < k; ++i) {
int x, y;
scanf("%d%d", &x, &y);
mp[x][y] = 1;
}
int ans = match();
// printf("ans = %d\n", ans);
int ret = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (mp[i][j]) {
mp[i][j] = 0;
// printf("%d %d match %d\n", i, j, match());
if (match() < ans) {
++ret;
}
mp[i][j] = 1;
}
}
}
++cnt;
printf("Board %d have %d important blanks for %d chessmen.\n", cnt, ret,
ans);
}
return 0;
}
本以为到这里就完了,但是根据这个博客,发现还有优化的余地
删除一条边以后，没有必要重新求删边后新的二分图的最大匹配，只需检查删边后的匹配中—>可不可以再找到新的增广链就可以了。这样，时间复杂度就进一步降低。
在判断是否存在增广路得时候，不能只以删除的匹配边的顶点作起点来找增广路 正确的方法是：以删边后新的二分图的所有未匹配顶点出发做增广，都找不到增广路，匹配不能再增加.
这说的很简单,但是写起来还是需要一点时间的,而且优化并不明显(主要是杭电的数据太弱了,上面的算法运行了46ms,下面的算法运行了30ms,也可能是我写丑了)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
#define ll long long
#define maxn 1010
#define maxm int(1e6) + 100
using namespace std;
bool mp[maxn][maxn];
int n, m, k;
int used[maxn], vis[maxn];
int used2[maxn], vis2[maxn], mark[maxn];
bool Find(int u, int dfn) {
for (int i = 1; i <= m; ++i) {
if (mp[u][i]) {
if (vis[i] != dfn) {
vis[i] = dfn;
if (!used[i] || Find(used[i], dfn)) {
used[i] = u;
return true;
}
}
}
}
return false;
}
int match() {
int ans = 0;
for (int i = 1; i <= m; ++i) {
vis[i] = 0;
used[i] = 0;
}
for (int i = 1; i <= n; ++i) {
if (Find(i, i)) {
++ans;
}
}
return ans;
}
bool Find2(int u, int dfn) { // 寻找新增广路
for (int i = 1; i <= m; ++i) {
if (mp[u][i]) {
if (vis2[i] != dfn) {
vis2[i] = dfn;
if (!used2[i] || Find2(used2[i], dfn)) { // 这里忘了写2,改了好久...
used2[i] = u;
return true;
}
}
}
}
return false;
}
bool check() { // 尝试寻找新的增广路
for (int i = 1; i <= n; ++i) {
if (!mark[i] && Find2(i, i)) {
return 1;
}
}
return 0;
}
int main() {
int cnt = 0;
while (scanf("%d%d%d", &n, &m, &k) != EOF) {
for (int i = 0; i <= max(n, m); ++i) {
for (int j = 0; j <= max(n, m); ++j) {
mp[i][j] = 0;
}
}
for (int i = 0; i < k; ++i) {
int x, y;
scanf("%d%d", &x, &y);
mp[x][y] = 1;
}
int ans = match();
int ret = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (mp[i][j] && used[j] == i) {
for (int i = 1; i <= n; ++i) {
mark[i] = 0;
}
for (int i = 1; i <= m; ++i) {
vis2[i] = 0;
used2[i] = used[i];
}
used2[j] = 0;
for (int i = 1; i <= m; ++i) {
mark[used2[i]] = 1;
}
mp[i][j] = 0;
if (!check()) { // 未找到新的增广路,则记录为关键点
++ret;
}
mp[i][j] = 1;
}
}
}
++cnt;
printf("Board %d have %d important blanks for %d chessmen.\n", cnt, ret,
ans);
}
return 0;
}
