BZOJ4554 HEOI2016游戏

网络流。

我一开始傻傻的将每条边与每一列连边，边权为联通块树，但是这样做是错的因为我们就在跑网络流中会忽略掉边和列的关系。

我们在做网络流题时一定要注意题目中给出的限制条件，一定要以限制条件建图！！！！

我们对每个联通块单独考虑，再在节点上对他所在的竖直联通块与水平联通块连线。

 #include<bits/stdc++.h>

 using namespace std;

 const int N=;

 char s[][];

 int n,m,t,sz;

 int belx[][],bely[][];

 int result[];

 bool match[][],used[*];

 bool dfs(int x)

 {

     for(int i=t+;i<=sz;++i)

     {

         if(match[x][i])

         {

             if(!used[i])

             {

                 used[i]=;

                 if(!result[i]||dfs(result[i]))

                 {

                     result[i]=x;

                     return ;

                 }

             }

         }

     }

     return ;

 }

 int main()

 {

     //freopen("game.in","r",stdin);

     //freopen("game.out","w",stdout);

     scanf("%d%d",&n,&m);

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

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

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

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

     {

         if(j==||s[i][j-]=='#') sz++;

         belx[i][j]=sz;

     }

     t=sz;

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

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

     {

         if(j==||s[j-][i]=='#') sz++;

         bely[j][i]=sz;

     }

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

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

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

             match[belx[i][j]][bely[i][j]]=;

     int ans=;

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

     {

         memset(used,,sizeof used);

         if(dfs(i)) ans++;

     }

     printf("%d\n",ans);

 }