BZOJ-2150: 部落战争

[文章目录]

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;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注