BZOJ2150: 部落战争

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2150

Solution

先把原来的图根据每个点能到达的位置建图，发现是有向无环图最小不相交路径覆盖，就直接用二分图做
最小不相交路径覆盖=原图点数-最大匹配
参考：http://endlesscount.blog.163.com/blog/static/821197872012622103810976/

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll int
#define N 3000
using namespace std;
inline ll read(){
    char ch=getchar(); ll x=0,f=1;
    while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}
struct edge{
    ll to,next;
}e[4*N];
ll head[N],flag[N],link[N],a[N][N],id[N][N],dx[5],dy[5];
ll n,m,tot,num,ans,r,c,x,y; char s[N];
void add(ll u,ll v){
    e[++tot]=(edge){v,head[u]}; head[u]=tot;
}
bool find(ll u){
    for (ll i=head[u],v=e[i].to;i;i=e[i].next,v=e[i].to)
        if (!flag[v]){
            flag[v]=1;
            if (!link[v]||find(link[v])){
                link[v]=u; return 1;
            }
        }
    return 0;
}
int main(){
    n=read(); m=read(); r=read(); c=read();
    dx[0]=r;dx[1]=r;dx[2]=c;dx[3]=c;  
        dy[0]=c;dy[1]=-c;dy[2]=r;dy[3]=-r;  
    for (ll i=1;i<=n;i++){
        scanf("%s",s+1);
        for (ll j=1;j<=m;j++)
            if (s[j]=='.') id[i][j]=++num,a[i][j]=1;
    }
    for (ll i=1;i<=n;i++)
    for (ll j=1;j<=m;j++)
        if (a[i][j]){
            for (ll k=0;k<4;k++){
                x=i+dx[k],y=j+dy[k];
                if (x<1||x>n||y<1||y>m) continue;
                if (a[x][y]) add(id[i][j],id[x][y]);
            }
        }
    for (ll i=1;i<=num;i++){
        memset(flag,0,sizeof flag);
        if (find(i)) ans++;
    }
    printf("%d",num-ans);
}