题解 P2172 【[国家集训队]部落战争】

· · 题解

这题与 [ TJOI2013攻击装置 ] 有点类似

不过此题中的军队只会向下走

注意最后的问题

至少要多少支军队才能完成统一全国的大业

所以这道题可以很容易的被我们转换成二分图匹配中的

最小路径覆盖

一开始每个点都是独立的为一条路径，总共有 n 条不相交路径。

我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径，

也就相当于路径数减少了1。

所以找到了几条匹配边，路径数就减少了多少。

所以有

最小路径覆盖=原图的结点数-新图的最大匹配数。

对于每个可以放军队的点

我们将军队一步能够走到的点和军队所在的点建边

进行二分图匹配

最后用是 . 的结点的个数-最大匹配数就是最后的答案了

采用匈牙利算法实现

#include<iostream>
#include<cstring>
#include<cstdio>
#define g(i,j) (i-1)*m+j
using namespace std;
const int maxn=1000000+10,maxl=1000000*2+10; 
int vis[maxn],n,m,link[maxn],head[maxn],cnt=0,t=0,r,c;
char a[60][60];
struct data
{
    int v,next;
}e[maxl];
inline void add(int u,int v)
{
    e[++cnt]=(data){v,head[u]};
    head[u]=cnt;
}
template<class T>inline void read(T &x)
{
    x=0;char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar(); 
}
int dx[10],dy[10];
bool find_(int u)
{
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].v;
        if(vis[v]!=t)
        {
            vis[v]=t;
            if(link[v]==-1||find_(link[v]))
            {
                link[v]=u;
                return true;
            }
        }
    }
    return false;
}
void get_char(char &x)
{
    x=getchar();
    while(x!='.'&&x!='x')x=getchar();
    return ;
}
int main()
{
    int ans=0;
    memset(link,-1,sizeof(link));
    read(n),read(m),read(r),read(c);
    dx[1]=r,dy[1]=c;
    dx[2]=r,dy[2]=-c;
    dx[3]=c,dy[3]=r;
    dx[4]=c,dy[4]=-r;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    get_char(a[i][j]);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    if(a[i][j]=='.'){
        for(int k=1;k<=4;k++)
        {
            int x=i+dx[k],y=j+dy[k];
            if(x<1||x>n||y<1||y>m||a[x][y]=='x')continue;
            add(g(i,j),g(x,y));
        }
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    if(a[i][j]=='.'){
        ++t;
        if(find_(g(i,j)))
        ans++;
    }
    printf("%d\n",t-ans);
}