Bzoj 2150(DAG的最小不相交路径覆盖)

Bzoj 2150
用二分图最大匹配求DAG的最小不相交路径覆盖,答案为 原图的节点数 $-$ 新图的二分图最大匹配。算是模板题,注意高山不能算点,要注意特判,具体解法看这里

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define Uint unsigned int
#define db double
using namespace std;
const int MAXN = 50 + 5;
int dx[4], dy[4];
int mp[MAXN][MAXN], num[MAXN][MAXN], m, n, R, C;
char s[MAXN];
int cnt, newn, lk[MAXN * MAXN], vis[MAXN * MAXN];
vector<int> G[MAXN * MAXN];
bool hungary(int u) {
for (Uint i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (vis[v] != cnt) {
vis[v] = cnt;
if (!lk[v] || hungary(lk[v])) {
lk[v] = u;
return true;
}
}
}
return false;
}
void clean() {
newn = 0, ms(mp, 0), ms(num, 0);
for (int i = 0; i <= n * n; i++) G[i].clear(), lk[i] = vis[i] = 0;
}
void solve() {
clean();
for (int i = 1; i <= m; i++) {
scanf("%s", s + 1);
for (int j = 1; j <= n; j++) {
if (s[j] == 'x') mp[i][j] = 1; else num[i][j] = ++newn;
//坐标转顶点编号新技巧,这里不能再用坐标转编号的数学方法了,因为是高山的话这里在新图中不算是一个点
}
}
dx[0] = R, dx[1] = R, dx[2] = C, dx[3] = C;
dy[0] = -C, dy[1] = C, dy[2] = -R, dy[3] = R;//偏移坐标
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (!mp[i][j])
for (int qaq = 0; qaq < 4; qaq++) {
int tx = dx[qaq] + i, ty = dy[qaq] + j;
if (tx > 0 && ty > 0 && tx <= m && ty <= n && !mp[tx][ty]) G[num[i][j]].push_back(num[tx][ty]);
}
}
}
int ans = 0;
for (int i = 1; i <= newn; i++) {
if (hungary(cnt = i)) ans++;
}
printf("%d\n", newn - ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%d%d%d%d", &m, &n, &R, &C), solve();
return 0;
}

------ 本文结束 ------