bzoj 1735: [Usaco2005 jan]Muddy Fields 泥泞的牧场 最小点覆盖

链接

1735: [Usaco2005 jan]Muddy Fields 泥泞的牧场

思路

这就是个上一篇的稍微麻烦版(是变脸版，其实没麻烦)
用边长为1的模板覆盖地图上的没有长草的土地，不能覆盖草地
每个点(x,y)只有选择x或者y才能被覆盖
还是最小点覆盖，证明在上一篇
横边和竖边得遍历一遍求出，因为不能越过草地嘛
然后左边横边，右边竖边，开心的跑最大流就可以

代码

#include <bits/stdc++.h>
#define iter vector<int>::iterator
using namespace std;
const int N=5e5+7,inf=0x3f3f3f3f;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,m,S,T;
struct node {
    int v,nxt,cap;
}e[N<<1];
int head[N<<1],tot=1;
void add_edge(int u,int v,int cap) {
    e[++tot].v=v;
    e[tot].cap=cap;
    e[tot].nxt=head[u];
    head[u]=tot;
}
void Add(int u,int v,int cap) {
    add_edge(u,v,cap);
    add_edge(v,u,0);
}
int dis[N];
bool bfs() {
    memset(dis,-1,sizeof(dis));
    queue<int> q;
    q.push(S);
    dis[S]=0;
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if(dis[v]==-1&&e[i].cap) {
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    return dis[T]!=-1;
}
int dfs(int u,int f) {
    if(u==T) return f;
    int rest=f;
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if(dis[v]==dis[u]+1&&e[i].cap&&rest) {
            int t=dfs(v,min(e[i].cap,rest));
            if(!t) dis[v]=0;
            e[i].cap-=t;
            e[i^1].cap+=t;
            rest-=t;
        }
    }
    return f-rest;
}
int dinic() {
    int ans=0;
    while(bfs())
        ans+=dfs(S,inf);
    return ans;
}
char s[100][100];
vector<int> dsr,mmp;
int a[100][100],b[100][100],js;
int main() {
    n=read(),m=read();
    for(int i=1;i<=n;++i) scanf("%s",s[i]+1);
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=m;++j) {
            if(s[i][j]=='.') continue;
            if(a[i][j-1]) a[i][j]=a[i][j-1];
            else {
                a[i][j]=++js;
                dsr.push_back(js);
            }
            if(b[i-1][j]) b[i][j]=b[i-1][j];
            else {
                b[i][j]=++js;
                mmp.push_back(js);  
            }
        }
    }
    S=501,T=502;
    for(iter i=dsr.begin();i!=dsr.end();++i) Add(S,*i,1);
    for(iter i=mmp.begin();i!=mmp.end();++i) Add(*i,T,1);
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=m;++j) {
            if(s[i][j]=='*') Add(a[i][j],b[i][j],1);
        }
    }
    printf("%d\n",dinic());
    return 0;
}