bzoj1735 [Usaco2005 jan]Muddy Fields 泥泞的牧场

传送门

分析

我们知道对于没有障碍的情况就是将横轴点于纵轴点连边

于是对于这种有障碍的情况我们还是分横轴纵轴考虑

只不过对于有障碍的一整条分为若干个无障碍小段来处理

然后将标号小段连边，跑最大匹配即可

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

int n,m,be1[][],be2[][],g[][],Ans,T,used[],belong[];

char s[][];

inline bool work(int x){

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

      if(used[i]!=T&&g[x][i]){

          used[i]=T;

          if(!belong[i]||work(belong[i])){

            belong[i]=x;

            return ;

        }

      }

    return ;

}

inline void go(){

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

      T=i;

      if(work(i))Ans++;

    }

}

int main(){

    int w,r,i,j,k;

    scanf("%d%d",&w,&r);

    for(i=;i<w;i++)

      scanf("%s",s[i]);

    for(i=;i<w;i++){

      k=;

      for(j=;j<r;j++){

          if(s[i][j]=='.'&&!k)k=;

          if(s[i][j]=='*'){

            if(k)n++,k=;

            be1[i][j]=n;

        }

      }

    }

    for(i=;i<r;i++){

      k=;

      for(j=;j<w;j++){

          if(s[j][i]=='.'&&!k)k=;

          if(s[j][i]=='*'){

            if(k)m++,k=;

            be2[j][i]=m;

        }

      }

    }

    for(i=;i<w;i++)

      for(j=;j<r;j++)

        g[be1[i][j]][be2[i][j]]=;

    go();

    cout<<Ans;

    return ;

}