jzoj4612. 【NOIP2016模拟7.12】游戏

菜鸡原来想的二分图最大集。。。但是分析一下就会发现有奇环。。。too naive

所以二分图集不可做

但是这题可以二分图匹配

我们可以考虑将每一个空地作为一条边，硬石头划分出的每一个横长条作为二分图的一边，竖长条作为另一边

然后可以考虑每一个空地，把空地对应的竖长条和横长条连一条边

这样子，每一个长条连的边就是组成它的空地，这些边在匹配中只能选1个，恰好和题目“每一个长条只能放置一个”的要求相同

最大匹配就是选最多的边，也就是放置最多的

真是巧妙，深深感觉自己的弱小

代码：

#include<bits/stdc++.h>
using namespace std;
int h[200050],nxt[200050],v[200050],w[200050],dep[20005],ec,m,n,ans,s,t,ct,i1[100][100],i2[100][100];
char c[100][100]; 
void add(int a,int b,int c){v[++ec]=b;w[ec]=c;nxt[ec]=h[a];h[a]=ec;}
void adj(int a,int b){add(a,b,1);add(b,a,0);}
bool bfs(){
    queue<int>q;q.push(s);memset(dep,0,sizeof(dep));dep[s]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=h[x];i;i=nxt[i])
            if(w[i]>0&&!dep[v[i]])
                dep[v[i]]=dep[x]+1,q.push(v[i]);
    }return dep[t];
}int dfs(int x,int dis){
    if(x==t||!dis)return dis;int tp=0;
    for(int i=h[x];i&&tp<dis;i=nxt[i])
        if(dep[v[i]]==dep[x]+1&&w[i]>0){
            int f=dfs(v[i],min(dis-tp,w[i]));
            w[i]-=f;w[i^1]+=f;tp+=f;
        }
    if(!tp)dep[x]=0;return tp;
}int din(){
    int aans=0;
    while(bfs())aans+=dfs(s,1e9);
    return aans;
}
int id(int a,int b){return b+(a-1)*m;}
int main(){
    ec=1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%s",c[i]+1);
    int ct=0,bd;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(c[i][j]!='#'){
                if(c[i][j-1]=='#'||j<2)ct++;
                i1[i][j]=ct;
            }
    bd=ct;
    for(int j=1;j<=m;j++)
        for(int i=1;i<=n;i++)
            if(c[i][j]!='#'){
                if(c[i-1][j]=='#'||i<2)ct++;
                i2[i][j]=ct;
            }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(c[i][j]=='*')
                adj(i1[i][j],i2[i][j]);
    t=ct+1;
    for(int i=1;i<=bd;i++)
        adj(s,i);
    for(int i=bd+1;i<=ct;i++)
        adj(i,t);
    printf("%d\n",din()); 
}