[BZOJ2150] 部落战争

描述 Description

lanzerb 的部落在 A 国的上部,他们不满天寒地冻的环境,于是准备向 A 国的下部征战来获得更大的领土。 A 国是一个 MN 的矩阵,其中某些地方是城镇,某些地方是高山深涧无人居住。lanzerb 把自己的部落分成若干支军队,他们约定: 1. 每支军队可以从任意一个城镇出发,并只能从上往向下征战,不能回头。途中只能经过城镇,不能经过高山深涧。 2. 如果某个城镇被某支军队到过,则其他军队不能再去那个城镇了。 3. 每支军队都可以在任意一个城镇停止征战。 4. 所有军队都很奇怪,他们走的方法有点像国际象棋中的马。不过马每次只能走 12 的路线,而他们只能走 R*C 的路线。 lanzerb 的野心使得他的目标是统一全国,但是兵力的限制使得他们在配备人手时力不从心。假设他们每支军队都能顺利占领这支军队经过的所有城镇,请你帮 lanzerb 算算至少要多少支军队才能完成统一全国的大业。

输入格式 InputFormat

第一行包含 4 个整数 M、N、R、C,意义见问题描述。接下来 M 行每行一个长度为 N 的字符串。如果某个字符是’.‘,表示这个地方是城镇;如果这个字符时’x’,表示这个地方是高山深涧。

输出格式 OutputFormat

输出一个整数,表示最少的军队个数。

样例输入 SampleInput

5 4 1 1
….
..x.
…x
….
x…

样例输出 SampleOutput

5


BZOJ 2150


每个点向可达点建边,最小路径覆盖。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=55;
int i,j,t,n,m,l,r,k,z,y,x;
struct edge
{
    int to,nx,vl;
}e[maxn*maxn*4];
int head[maxn*maxn],match[maxn*maxn],id[maxn][maxn];
bool used[maxn*maxn];
int sum,cnt,mat,c;
char ch[maxn];
inline void ins(int u,int v)
{
    e[++cnt].to=v;e[cnt].nx=head[u];
    head[u]=cnt;
}
inline void jud(int s,int x,int y)
{
    if (x<=0 || y<=0 || x>m || y>n) return ;
    if (id[x][y]) ins(s,id[x][y]);
}
bool crosspath(int s)
{
    int i,j,t,u,v,w;
    for (i=head[s];i;i=e[i].nx)
    {
        v=e[i].to;
        if (!used[v])
        {
            used[v]=true;
            if (!match[v] || crosspath(match[v]))
            {
                match[v]=s;
                return true;
            }
        }
    }
    return false;
}
inline void hungary()
{
    int i,j,t;
    for (i=1;i<=sum;i++)
    {
        memset(used,false,sizeof(used));
        if (crosspath(i)) mat++;
    }
}
int main()
{
    sum=cnt=mat=0;
    memset(id,0,sizeof(id));
    memset(match,0,sizeof(match));
    scanf("%d%d%d%d",&m,&n,&r,&c);
    for (i=1;i<=m;i++)
    {
        scanf("%s",ch);
        for (j=0;j<n;j++) if (ch[j]=='.') id[i][j+1]=++sum;
    }
    for (i=1;i<=m;i++) for (j=1;j<=n;j++) if (id[i][j])
    {
        jud(id[i][j],i+r,j-c);jud(id[i][j],i+c,j-r);
        jud(id[i][j],i+r,j+c);jud(id[i][j],i+c,j+r);
    }
    hungary();
    printf("%d\n",sum-mat);
    return 0;
}