题目描述
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
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=,N=;
char ch;
bool g[][]={};//(x-1)*n+y
bool vis[]={};
struct men{
int lover;
std::vector<int> t;
}man[]; int woman[]={}; bool dfs(int u)
{
int sz=man[u].t.size();
for(int i=;i<sz;i++)
{
int w=man[u].t[i];
if(!vis[w])
{
vis[w]=;
if(!woman[w]||dfs(woman[w]))
{
woman[w]=u;
man[u].lover=w;
return ;
}
}
}
return ;
}
int main()
{
//freopen("lanzerb.in","r",stdin);
//freopen("lanzerb.out","w",stdout);
scanf("%d %d %d %d",&m,&n,&r,&c);
for(int i=;i<=m;i++)
{
for(int j=;j<=n;j++)
{
scanf("\n%c",&ch);
if(ch=='.')
g[i][j]=,N++;
}
}
int bh[][]={{r,c},{c,-r},{c,r},{r,-c}};
for(int i=;i<=m;i++)
{
for(int j=;j<=n;j++)
{
if(!g[i][j]) continue;
int id=(i-)*n+j;
for(int k=;k<;k++)
{
if(r==c&&k>) break;
int x=i+bh[k][],y=j+bh[k][];
if(x>=&&x<=m&&y>=&&y<=n&&g[x][y])
{
man[id].t.push_back((x-)*n+y);
}
}
}
}
memset(woman,,sizeof(woman));
for(int i=;i<=n*m;i++)
{
memset(vis,,sizeof(vis));
if(dfs(i))
ans++;
}
printf("%d\n",N-ans);
return ;
}