Description:
lanzerb的部落在A国的上部，他们不满天寒地冻的环境，于是准备向A国的下部征战来获得更大的领土。 A国是一个 \(M\times N\) 的矩阵，其中某些地方是城镇，某些地方是高山深涧无人居住。lanzerb把自己的部落分成若干支军队，他们约定： 1. 每支军队可以从任意一个城镇出发，并只能从上往向下征战，不能回头。途中只能经过城镇，不能经过高山深涧。 2. 如果某个城镇被某支军队到过，则其他军队不能再去那个城镇了。 3. 每支军队都可以在任意一个城镇停止征战。 4. 所有军队都很奇怪，他们走的方法有点像国际象棋中的马。不过马每次只能走 \(1\times 2\) 的路线，而他们只能走 \(R\times C\) 的路线。 lanzerb的野心使得他的目标是统一全国，但是兵力的限制使得他们在配备人手时力不从心。假设他们每支军队都能顺利占领这支军队经过的所有城镇，请你帮lanzerb算算至少要多少支军队才能完成统一全国的大业。
Input:
第一行包含4个整数M、N、R、C，意义见问题描述。接下来M行每行一个长度为N的字符串。如果某个字符是'.'，表示这个地方是城镇；如果这个字符时'x'，表示这个地方是高山深涧。
Output:
输出一个整数，表示最少的军队个数。
Sample Input:
| 1 2 3 4 5 | 3 3 1 2 ... .x. ... |
Sample Output:
| 1 2 | 4 |
题解：
这道题建模还是有一点难度的～～～
我们把每一个非x点视为一个点，若u能到达v则连一条边。
因为每一次只能向下运动，所以不能回到原来的点，原图一定是一个DAG。
题目即求该DAG的最小路径覆盖（即最少的路径覆盖全部的点）
因为最小路径覆盖等于最长反链（即最大的点集其中任意两点均不可到达）
所以我们将DAG转化为二分图通过最大匹配求最长反链。（即建立两个点集，若u到v有一条边，从x方点u连向y方点v）
答案=原图点数-最大匹配数
代码如下：
| 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 | /* ID: Sunshine_cfbsl PROG: BZOJ2150 LANG: C++ */ #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN = 2510; int m, n, r, c, id[55][55], en, to[MAXN<<2]; int dr[4][2], N, Begin[MAXN], Next[MAXN<<2]; int linkx[MAXN], linky[MAXN], ans; bool vis[MAXN]; char s[55][55]; inline int read() { int x = 0, f = 1; char ch = getchar(); for(; ch<'0' || ch>'9'; ch=getchar()) if(ch=='-') f=-1; for(; ch>='0'&&ch<='9'; ch=getchar()) x = x*10 + ch-'0'; return x * f; } inline int ID(int i, int j) { if(id[i][j] == 0) id[i][j] = ++N; return id[i][j]; } inline void Add(int u, int v) { to[++en] = v; Next[en] = Begin[u]; Begin[u] = en; } bool dfs(int u) { int i; vis[u] = true; for(i = Begin[u]; i; i = Next[i]) { int v = to[i]; if(!linky[v] || (!vis[linky[v]]&&dfs(linky[v]))) { linky[linkx[u]=v] = u; return true; } } return false; } int main() { int i, j, k; m = read(), n = read(); r = read(), c = read(); dr[0][0] = r, dr[0][1] = c; dr[1][0] = r, dr[1][1] = -c; dr[2][0] = c, dr[2][1] = r; dr[3][0] = c, dr[3][1] = -r; for(i = 1; i <= m; i++) scanf("%s", s[i]+1); for(i = 1; i <= m; i++) { for(j = 1; j <= n; j++) { if(s[i][j] == 'x') continue; ID(i, j); for(k = 0; k < (r==c? 2 : 4); k++) { int x = i+dr[k][0], y = j+dr[k][1]; if(x<1 || x>m || y<1 || y>n) continue; if(s[x][y] == 'x') continue; Add(ID(i, j), ID(x, y)); } } } ans = N; for(i = 1; i <= N; i++) { if(!linkx[i]) { memset(vis, false, sizeof(vis)); ans -= dfs(i); } } printf("%d\n", ans); return 0; } |
