题解 P6062 【[USACO05JAN]Muddy Fields G】

JK_LOVER · 2020-08-08 20:18:16 · 题解

题意

一个 R\times C 的网格图，求最小需要多少个宽度为 1 的矩形完美覆盖，可以重叠。QWQ

分析

我们发现如果有一个横着的矩形右边仍然有泥地，那么完全可以延长这个矩形。即使这个泥地已经被其他矩形覆盖了，这是不会使答案变劣的。

• 有了上面的分析，我们就可以很轻松的想到一个泥地只能被两种矩形覆盖 1：横着的，2：竖着的。

• 而横着和竖着的矩形只需要一个就可以了，这个就是标准的二分图模型了，那么根据最大流最小割定理，只要把覆盖到同一方格的两个矩形连边。跑最大流就完成了。

• 小细节：虽然 R,C\le50 但矩形种类可能达到 R\times C 级别的，数组一定要开够。

  代码

  
  #include<bits/stdc++.h>
  using namespace std;
  const int N = 101210;
  int read(){int x;scanf("%d",&x);return x;}
  struct Edge{int to,nxt,flow,cap;}e[N<<1];
  int cnt = 1,R,C,S,T,cur[N],head[N],dis[N];
  queue<int> Q;
  void add(int x,int y,int cap){
  e[++cnt].nxt = head[x];e[cnt].to = y;e[cnt].flow = 0;e[cnt].cap = cap;head[x] = cnt;
  e[++cnt].nxt = head[y];e[cnt].to = x;e[cnt].flow = 0;e[cnt].cap = 0;head[y] = cnt;
  }
  bool bfs(int s,int t){
  while(!Q.empty()) Q.pop();
  memset(dis,0,sizeof(dis));dis[s] = 1;Q.push(s);
  while(Q.size()){
      int x = Q.front();Q.pop();
      for(int i = head[x];i;i = e[i].nxt){
          if(!dis[e[i].to] && e[i].cap > e[i].flow){
              Q.push(e[i].to);dis[e[i].to] = dis[x] + 1;
              if(e[i].to == t) return true;
          }
      }
  }
  return false;
  }
  int dfs(int x,int a,int t){
  if(x == t|| a == 0) return a;
  int flow = 0,f;
  for(int i = cur[x];i;i = e[i].nxt){
      int y = e[i].to;
      if(dis[y] == dis[x] + 1 && (f=dfs(y,min(a,e[i].cap-e[i].flow),t))>0)        
      {
          e[i].flow += f;e[i^1].flow -= f;flow += f;a -= f;cur[x] = i;
          if(!a) break; 
      }
  }
  return flow;
  }
  char ch[55][55];
  int col[550][550][2],Colx,Coly,vis[550][510];
  int main()
  {
  R = read();C = read();
  for(int i = 1;i <= R;i++){
      for(int j = 1;j <= C;j++){
          cin>>ch[i][j];
          if(ch[i][j]=='*' && ch[i-1][j] == '*') 
          col[i][j][1] = col[i-1][j][1];
          else if(ch[i][j]=='*')col[i][j][1] = ++Colx;
          if(ch[i][j]=='*' && ch[i][j-1] == '*') 
          col[i][j][0] = col[i][j-1][0];
          else if(ch[i][j]=='*')col[i][j][0] = ++Coly;
      }
  }
  S = 0;T = Colx+Coly+1;
  for(int i = 1;i <= Colx;i++) add(S,i,1);
  for(int i = 1;i <= Coly;i++) add(i+Colx,T,1);
  for(int i = 1;i <= R;i++){
      for(int j = 1;j <= C;j++){  
          if(ch[i][j]=='.') continue;
          int y = col[i][j][0],x = col[i][j][1];
          if(!vis[x][y]) add(x,y+Colx,1),vis[x][y] = 1;
      }
  }
  int maxflow = 0;
  while(bfs(S,T)){
      for(int i = 0;i < T;i++) cur[i] = head[i];
      maxflow += dfs(S,0x3f3f3f3f,T);
  }
  printf("%d\n",maxflow);
  return 0;
  }