题目
题目描述
lanzerb的部落在A国的上部，他们不满天寒地冻的环境，于是准备向A国的下部征战来获得更大的领土。
A国是一个M*N的矩阵，其中某些地方是城镇，某些地方是高山深涧无人居住。lanzerb把自己的部落分成若干支军队，他们约定：
每支军队可以从任意一个城镇出发，并只能从上往向下征战，不能回头。途中只能经过城镇，不能经过高山深涧。
如果某个城镇被某支军队到过，则其他军队不能再去那个城镇了。
每支军队都可以在任意一个城镇停止征战。
所有军队都很奇怪，他们走的方法有点像国际象棋中的马。不过马每次只能走12的路线，而他们只能走RC的路线。
lanzerb的野心使得他的目标是统一全国，但是兵力的限制使得他们在配备人手时力不从心。假设他们每支军队都能顺利占领这支军队经过的所有城镇，请你帮lanzerb算算至少要多少支军队才能完成统一全国的大业。
输入输出格式
输入格式：
第一行包含4个整数M、N、R、C，意义见问题描述。接下来M行每行一个长度为N的字符串。如果某个字符是’.’，表示这个地方是城镇；如果这个字符时’x’，表示这个地方是高山深涧。
输出格式：
输出一个整数，表示最少的军队个数。
输入输出样例
输入样例#1：
3 3 1 2
...
.x.
...
输出样例#1：
4
输入样例#2：
5 4 1 1
....
..x.
...x
....
x...
输出样例#2：
5
说明
100%的数据中，1<=M,N<=50，1<=R,C<=10。
题解
因为每个点只让过一次，还可以从任意一个点出发或结束
考虑网络流的最小路径覆盖
把每个点一分为二，源点与每个点的入点连容量为$1$的边，每个点的出点与汇点连容量为$1$的边
这样可以保证从任意一个点出发或结束
每个点的入点与它能到达的点的出点连容量为$1$的边
有这样一个结论：
路径覆盖中的每条简单路径除了最后一个顶点之外都有唯一的后继和它对应；因此匹配边数就是非路径结尾的结点数；因此，匹配边数达到最大时，非路径结尾的结点数大道最大，故路径结尾的节点数目最少
跑最大流就行了，最后输出'.'的总数-最大流
代码
# include<iostream>
# include<cstdio>
# include<cstring>
# include<queue>
# define pu(x,y) (x-1)*m+y
using namespace std;
const int MAX=100001,t=100000,inf=1e8;
struct p{
int x,y,dis;
}c[MAX<<1];
int n,m,R,C,num,tot,SUM;
int h[MAX],d[MAX],pre[MAX];
char a[51][51];
void add(int x,int y,int dis)
{
c[num]=(p){h[y],x,0};
h[y]=num++;
c[num]=(p){h[x],y,dis};
h[x]=num++;
}
int dfs(int x,int dix)
{
if(!dix||x==t) return dix;
int sum=0;
for(int i=h[x];i;i=c[i].x)
if(d[c[i].y]==d[x]+1&&c[i].dis)
{
int dis=dfs(c[i].y,min(c[i].dis,dix));
if(dis)
{
dix-=dis;
sum+=dis;
c[i].dis-=dis;
c[i^1].dis+=dis;
if(!dix) break;
}
}
if(!sum) d[x]=-2;
return sum;
}
bool bfs()
{
queue<int> qu;
qu.push(0);
memset(d,0,sizeof(d));
d[0]=1;
while(!qu.empty())
{
int tt=qu.front();
qu.pop();
for(int i=h[tt];i;i=c[i].x)
if(!d[c[i].y]&&c[i].dis)
{
d[c[i].y]=d[tt]+1;
qu.push(c[i].y);
}
}
return d[t];
}
int dinic()
{
int tot=0;
while(bfs()) tot+=dfs(0,inf);
return tot;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&R,&C);
int ff=pu(n,m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]=='.')
{
SUM++;
int hh=pu(i,j),x,y;
x=i+R,y=j+C;
if(a[x][y]=='.'&&x>=1&&y>=1&&x<=n&&y<=m)
add(hh,pu(x,y)+ff,1);
x=i+R,y=j-C;
if(a[x][y]=='.'&&x>=1&&y>=1&&x<=n&&y<=m)
add(hh,pu(x,y)+ff,1);
x=i+C,y=j+R;
if(a[x][y]=='.'&&x>=1&&y>=1&&x<=n&&y<=m)
add(hh,pu(x,y)+ff,1);
x=i+C,y=j-R;
if(a[x][y]=='.'&&x>=1&&y>=1&&x<=n&&y<=m)
add(hh,pu(x,y)+ff,1);
add(0,hh,1),add(hh+ff,t,1);
}
printf("%d",SUM-dinic());
return 0;
}
