题目描述
lanzerb的部落在A国的上部，他们不满天寒地冻的环境，于是准备向A国的下部征战来获得更大的领土。 A国是一个M*N的矩阵，其中某些地方是城镇，某些地方是高山深涧无人居住。lanzerb把自己的部落分成若干支军队，他们约定： 1. 每支军队可以从任意一个城镇出发，并只能从上往向下征战，不能回头。途中只能经过城镇，不能经过高山深涧。 2. 如果某个城镇被某支军队到过，则其他军队不能再去那个城镇了。 3. 每支军队都可以在任意一个城镇停止征战。 4. 所有军队都很奇怪，他们走的方法有点像国际象棋中的马。不过马每次只能走1*2的路线，而他们只能走R*C的路线。 lanzerb的野心使得他的目标是统一全国，但是兵力的限制使得他们在配备人手时力不从心。假设他们每支军队都能顺利占领这支军队经过的所有城镇，请你帮lanzerb算算至少要多少支军队才能完成统一全国的大业。
输入
第一行包含4个整数M、N、R、C，意义见问题描述。接下来M行每行一个长度为N的字符串。如果某个字符是'.'，表示这个地方是城镇；如果这个字符时'x'，表示这个地方是高山深涧。
输出
输出一个整数，表示最少的军队个数。
样例输入
【样例输入一】
3 3 1 2
...
.x.
...
【样例输入二】
5 4 1 1
....
..x.
...x
....
x...
3 3 1 2
...
.x.
...
【样例输入二】
5 4 1 1
....
..x.
...x
....
x...
样例输出
【样例输出一】
4
【样例输出二】
5
【样例说明】
【数据范围】
100%的数据中，1<=M,N<=50，1<=R,C<=10。
4
【样例输出二】
5
【样例说明】
【数据范围】
100%的数据中，1<=M,N<=50，1<=R,C<=10。
提示
来源
//BZOJ没有，我来加个：国家集训队2011
吐槽
n和m都小于50，空间至少要开到50*50=2500！
解题思路
一道最小路径覆盖的题目，可以按照题意建图，对于点$(i,j)$，向$(i+r,j+c)$、$(i+r,j-c)$、$(i+c,j+r)$、$(i+c,j-r)$连单向边(前提是点在地图上且是城市)，然后跑最小路径覆盖即可，我依然跑匈牙利，这提数据范围用不到dinic，但是dinic跑得快。
源代码
#include<cstdio> #include<vector> #include<cstring> int m,n,r,c,ans=0,N=0; char ch; bool g[2510][2510]={0};//(x-1)*n+y bool vis[2510]={0}; struct men{ int lover; std::vector<int> t; }man[2510]; int woman[2510]={0}; bool dfs(int u) { int sz=man[u].t.size(); for(int i=0;i<sz;i++) { int w=man[u].t[i]; if(!vis[w]) { vis[w]=1; if(!woman[w]||dfs(woman[w])) { woman[w]=u; man[u].lover=w; return 1; } } } return 0; } int main() { //freopen("lanzerb.in","r",stdin); //freopen("lanzerb.out","w",stdout); scanf("%d %d %d %d",&m,&n,&r,&c); for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { scanf("\n%c",&ch); if(ch=='.') g[i][j]=1,N++; } } int bh[4][2]={{r,c},{c,-r},{c,r},{r,-c}}; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(!g[i][j]) continue; int id=(i-1)*n+j; for(int k=0;k<4;k++) { if(r==c&&k>1) break; int x=i+bh[k][0],y=j+bh[k][1]; if(x>=1&&x<=m&&y>=1&&y<=n&&g[x][y]) { man[id].t.push_back((x-1)*n+y); } } } } memset(woman,0,sizeof(woman)); for(int i=1;i<=n*m;i++) { memset(vis,0,sizeof(vis)); if(dfs(i)) ans++; } printf("%d\n",N-ans); return 0; }
