[GCJ 2021 #3] Square Free 题解

FFTotoro · 2025-07-04 15:08:29 · 题解

网络流题。看到这种限制行和与列和的题目，考虑网络流建模：对于每一行、每一列建立一个点，源点向行对应的点连流量为行和的边，列对应的点向汇点连流量为列和的边，行列之间连流量为 1 的边，跑最大流就可以得出一组不考虑“正方形”的方案。判断无解很容易，只需要检查一下最大流是否等于整个网格需要的 / 的个数即可。

剩下情况均为有解，因为可以通过如下的方式将让所有“正方形”消失：考虑把一对相邻行出现的 /...\（上一行）\.../（下一行）全部变成 \.../（上一行）/...\（下一行），就能拆掉一个可能的正方形，并且不会影响行列和的条件。但是可能会出现新的正方形，于是每次就暴力找可以拆的——最多会拆 O((RC)^2) 次（而且常数极小），直接模拟时间复杂度就是对的。

放代码：

#include<bits/stdc++.h>
using namespace std;
namespace IAOI_lib{
  template<typename C> class mf_graph{
    private:
      typedef pair<int,int> pii;
      int n;
      vector<vector<pii> > g;
      inline void add(int u,int v,C w){
        g[u].emplace_back(v,e.size());
        e.emplace_back(u,v,w,0);
      }
    public:
      struct edge{
        int u,v; C c,f;
        edge(int u,int v,C c,C f):u(u),v(v),c(c),f(f){}
      };
      vector<edge> e;
      mf_graph(int n):n(n),g(n){}
      inline void add_edge(int u,int v,C w){
        add(u,v,w),add(v,u,0);
      }
      edge get_edge(int x){return e[x<<1];}
      vector<edge> edges(){
        vector<edge> r;
        for(int i=0;i<e.size();i+=2)
          r.emplace_back(e[i]);
        return r;
      }
      C flow(int s,int t,C l=numeric_limits<C>::max()){
        C r=0;
        vector<int> d(n),p(n);
        auto dfs=[&](auto &&self,int u,C l)->C{
          if(u==t)return l;
          C r=0;
          for(int &i=p[u];i<g[u].size();i++){
            auto [v,x]=g[u][i];
            if(d[v]==d[u]+1&&e[x].c>e[x].f){
              C f=self(self,v,min(l-r,e[x].c-e[x].f));
              if(f){
                e[x].f+=f,e[x^1].f-=f,r+=f;
                if(l==r)return r;
              }
            }
          }
          return d[u]=-1,r;
        };
        while(1){
          fill(d.begin(),d.end(),-1),d[s]=0;
          queue<int> q; q.emplace(s);
          while(!q.empty()){
            int u=q.front(); q.pop();
            for(auto [i,x]:g[u])
              if(d[i]<0&&e[x].c>e[x].f)
                d[i]=d[u]+1,q.emplace(i);
          }
          if(d[t]<0)break;
          fill(p.begin(),p.end(),0);
          C f=dfs(dfs,s,l-r);
          if(!f)break;
          r+=f;
        }
        return r;
      }
  }; // 网络最大流模板
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int tt; cin>>tt;
  for(int t=1;t<=tt;t++){
    int n,m; cin>>n>>m;
    IAOI_lib::mf_graph<int> g(n+m+2);
    vector<int> a(n),b(m);
    for(int i=0;i<n;i++)
      for(int j=0;j<m;j++)
        g.add_edge(i,j+n,1);
    for(int i=0;i<n;i++)
      cin>>a[i],g.add_edge(n+m,i,a[i]);
    for(int i=0;i<m;i++)
      cin>>b[i],g.add_edge(i+n,n+m+1,b[i]);
    int f=g.flow(n+m,n+m+1); // 跑最大流
    cout<<"Case #"<<t<<": ";
    if(f!=accumulate(a.begin(),a.end(),0)
      ||f!=accumulate(b.begin(),b.end(),0)){
      cout<<"IMPOSSIBLE\n"; continue;
    } // 无解情况
    auto e=g.edges();
    vector<string> s(n,string(m,'\\'));
    for(int i=0;i<n;i++)
      for(int j=0;j<m;j++)
        if(e[i*m+j].f)s[i][j]='/';
    while(1){
      bool f=true;
      for(int xa=0;xa<n-1;xa++)
        for(int ya=0;ya<m;ya++){
          int xb=xa+1;
          for(int yb=ya+1;yb<m&&f;yb++)
            if(s[xa][ya]=='/'&&s[xa][yb]=='\\'&&s[xb][ya]=='\\'&&s[xb][yb]=='/')
              swap(s[xa][ya],s[xa][yb]),swap(s[xb][ya],s[xb][yb]),f=false;
        }
      if(f)break;
    } // 暴力模拟拆正方形
    cout<<"POSSIBLE\n";
    for(auto i:s)cout<<i<<'\n';
  }
  return 0;
}