P2172 [国家集训队]部落战争（最小路径覆盖）

P2172 [国家集训队]部落战争

每个点仅走一次：最小路径覆盖

套路地拆点，具体看代码中的$draw()$

流量每增加1，意味着一支军队可以多走一格，代价减少1

最后答案即为总点数$-dinic()$

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>'') f=f&&(c!='-'),c=getchar();

    while(''<=c&&c<='') x=x*+c-,c=getchar();

    return f?x:-x;

}

#define M 400000

int n,m,R,C,S,T,d[M],cur[M],tt;

char q[][]; bool vis[M];

int Cnt=,hd[M],nxt[M],ed[M],poi[M],val[M];

void adde(int x,int y,int v){

    nxt[ed[x]]=++Cnt; hd[x]=hd[x]?hd[x]:Cnt;

    ed[x]=Cnt; poi[Cnt]=y; val[Cnt]=v;

}

void link(int x,int y,int v){adde(x,y,v),adde(y,x,);}

#define to poi[i]

bool Bfs(){

    memset(vis,,sizeof(vis));

    queue <int> h; h.push(S);

    vis[S]=; d[S]=;

    while(!h.empty()){

        int x=h.front(); h.pop();

        for(int i=hd[x];i;i=nxt[i])

            if(!vis[to]&&val[i]>)

                vis[to]=,d[to]=d[x]+,h.push(to);

    }return vis[T];

}

int Dfs(int x,int a){

    if(!a||x==T) return a;

    int F=,f;

    for(int &i=cur[x];i;i=nxt[i])

        if(d[to]==d[x]+&&(f=Dfs(to,min(a,val[i])))>){

            F+=f,a-=f,val[i]-=f,val[i^]+=f;

            if(!a) break;

        }

    return F;

}

int Dinic(){

    int re=;

    while(Bfs()){

        for(int i=;i<=T;++i) cur[i]=hd[i];

        re+=Dfs(S,1e9);

    }return re;

}

bool is(int x,int y){return x>&&x<=n&&y>&&y<=m&&q[x][y]=='.';}

int id(int x,int y){return x*m-m+y;}

void draw(int x,int y){

    int p=id(x,y); ++tt; link(S,p,); link(p+n*m,T,);

    if(is(x+R,y+C)) link(p,id(x+R,y+C)+n*m,);

    if(is(x+R,y-C)) link(p,id(x+R,y-C)+n*m,);

    if(is(x+C,y+R)) link(p,id(x+C,y+R)+n*m,);

    if(is(x+C,y-R)) link(p,id(x+C,y-R)+n*m,);

}

int main(){

    scanf("%d%d%d%d",&n,&m,&R,&C); S=n*m*+; T=S+;

    for(int i=;i<=n;++i) scanf("%s",q[i]+);

    for(int i=;i<=n;++i)

        for(int j=;j<=m;++j)

            if(q[i][j]=='.') draw(i,j);

    printf("%d\n",tt-Dinic());

    return ;

}