先说说为什么比标准答案多1。
我是把坐标(x,y) map成一个整数的,(x-1)*n+y-1,但是这样(1, 1)就变成0了。
我们是假设所有点从1开始才能这样check。看下面的comment。
如果你也遇到了这样的问题,看看是不是这个方面。
bool find(int u) {
for (int i = adjList[u]; ~i; i = ne[i]) {
int v = e[i];
if (st[v])
continue;
st[v] = 1;
// 这一行会出问题
if (match[v] == 0 || find(match[v])) {
match[v] = u;
return true;
}
}
return false;
}
下面开始要点小结。
这题一开始怎么也想不到二分图。我自己有一个错误的想法,如下:
我们把骨牌看成A集合的点,把棋盘上的位置看成B集合的点,每个骨牌都能放每一个位置,这就是边。
这种建图的问题是,我们锁定一个位置时,它的一半可能被其他牌match了,这个一半太讨厌了,没办法套匈牙利算法的模板。
所以y老师的建图思想是:把棋盘上的格子间隔着色,很容易证明这些不同颜色的格子就是二分图。注意,匈牙利算法的前提是图是二分图。然后我们把相邻的不同颜色的格子连边。这张图就能套匈牙利算法的模板了。
代码如下,这是我自己的写法,比y老师的麻烦一点因为我建图了。
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const int MOD = 1e9+7;
typedef pair<int, int> PII;
const int N = 105;
const int M = 4*N*N;
int adjList[N*N], e[M], ne[M], idx;
int m, n;
int st[N*N], match[N*N];
int grid[N][N];
int dirs[4][4] = {{0,1},{0,-1},{-1,0},{1,0}};
void add(int a, int b) {
e[idx] = b;
ne[idx] = adjList[a];
adjList[a] = idx++;
}
bool find(int u) {
for (int i = adjList[u]; ~i; i = ne[i]) {
int v = e[i];
if (st[v])
continue;
st[v] = 1;
if (match[v] == 0 || find(match[v])) {
match[v] = u;
return true;
}
}
return false;
}
int get(int x, int y) {
return (x-1) * n + y;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
memset(adjList, -1, sizeof adjList);
cin >> n >> m;
while (m--) {
int a, b;
cin >> a >> b;
grid[a][b] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if ((i + j) % 2 == 1)
continue;
if (grid[i][j])
continue;
for (int k = 0; k < 4; k++) {
int x = i + dirs[k][0];
int y = j + dirs[k][1];
if (x > n || y > n || x <= 0 || y <= 0)
continue;
if (grid[x][y])
continue;
int a = get(i, j);
int b = get(x, y);
add(a, b);
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if ((i + j) % 2 == 1)
continue;
memset(st, 0, sizeof st);
if (find(get(i, j)))
ans++;
}
}
cout << ans;
return 0;
}