[文章目录]
Description
lanzerb的部落在A国的上部，他们不满天寒地冻的环境，于是准备向A国的下部征战来获得更大的领土。 A国是一个M*N的矩阵，其中某些地方是城镇，某些地方是高山深涧无人居住。lanzerb把自己的部落分成若干支军队，他们约定： 1. 每支军队可以从任意一个城镇出发，并只能从上往向下征战，不能回头。途中只能经过城镇，不能经过高山深涧。 2. 如果某个城镇被某支军队到过，则其他军队不能再去那个城镇了。 3. 每支军队都可以在任意一个城镇停止征战。 4. 所有军队都很奇怪，他们走的方法有点像国际象棋中的马。不过马每次只能走1*2的路线，而他们只能走R*C的路线。 lanzerb的野心使得他的目标是统一全国，但是兵力的限制使得他们在配备人手时力不从心。假设他们每支军队都能顺利占领这支军队经过的所有城镇，请你帮lanzerb算算至少要多少支军队才能完成统一全国的大业。n,m<=50
不重复覆盖点的最小链覆盖。点数减去原图的最大匹配即为答案。
【一开始放了点数个链，每找到一个匹配即少一条链】
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,s,t,r,c,ans;
char mp[60][60];
inline int id(int x,int y){return x*m-m+y;}
int head[6000],to[50000],nxt[50000],f[50000],cnt=1;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
queue<int>q;
int dis[6000];
bool bfs()
{
memset(dis,-1,sizeof dis);
while(!q.empty()) q.pop();
q.push(s); dis[s]=0; int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) break;
}
return flow-tmp;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&r,&c);
int dx[]={c,r,r,c},dy[]={-r,-c,c,r};
for(int i=1;i<=n;++i) scanf("%s",mp[i]+1);
int x,y; s=0; t=n*m*2+1;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) if(mp[i][j]=='.')
{
ans++;
add(s,id(i,j),1); add(id(i,j)+n*m,t,1);
for(int k=0;k!=4;++k)
{
x=i+dx[k]; y=j+dy[k];
if(x>=1&&x<=n&&y>=1&&y<=m&&mp[x][y]=='.')
add(id(i,j),id(x,y)+n*m,1);
}
}
while(bfs()) ans-=dinic(s,inf);
printf("%d",ans);
return 0;
}