[GCJ 2019 #3] Datacenter Duplex 题解

· · 题解

这题很 6。

以下定义“边界”为满足 i=1\lor i=R\lor j=1\lor j=C 的格子 (i,j)，即四边上的格子。

考虑如果最终某个颜色没有连通（不妨设为颜色 \text{A}），只可能是如下的情况：

注意到一个事情：如果用新建的走廊把两个已经连通的格子连起来必然没用；在之后的构造中不会去做这样的事情。这样就解决了情况 1，即除非一开始就存在这样的环（此时必然无解），不然在之后的连边中不可能造出一个新的环。

对于情况 2，考虑开始时边界上一圈的颜色分布情况。直接摆出结论：特判完情况 1 后，有解当且仅当边界上所有颜色 \text{A} 连通且所有颜色 \text{B} 连通。证明：不妨认为若干个 \text{B} 在两段 \text{A} 的中间，要想让两个 \text{A} 连通就必然会把这些 \text{B} 和另外的 \text{B} 隔开（连接两段 \text{A} 的路径会把这一段 \text{B}“包住”），必然无解；否则无解只可能是情况 2，然而前面提到了“不会连通两个已经连通的格子”，所以若要产生一条情况 2 所述的路径，必然要产生一个新的环（这条路径让两个边界上连通的点“再次”连通，故产生了环），矛盾，所以必然有解。

于是考虑对于每个 2\times 2 方格考虑，依次考虑正副两条对角线上的两对格子，若存在一对未连通的就连起来，若存在两对未连通的就随便选一对（上面的证明已经说明了这里的不同选择不会导致有无解的结果不同），用并查集维护最后检查一下是否满足条件即可。时间复杂度 O(RC\alpha(RC))。

放代码：

#include<bits/stdc++.h>
using namespace std;
namespace IAOI_lib{
  template<typename T> class dsu{
    private:
      vector<T> a;
      vector<int> s;
    public:
      dsu(int n=2e5){
        a.resize(n),s.resize(n,1);
        iota(a.begin(),a.end(),0);
      }
      T leader(T x){
        return a[x]==x?x:a[x]=leader(a[x]);
      }
      inline int size(T x){
        return s[leader(x)];
      }
      inline void merge(T x,T y){
        x=leader(x),y=leader(y);
        if(x==y)return;
        if(s[x]>s[y])swap(x,y);
        s[y]+=s[x],a[x]=y;
      }
      inline bool same(T x,T y){
        return leader(x)==leader(y);
      }
  }; // 并查集模板
}
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,c=0; cin>>n>>m;
    vector<string> a(n);
    for(auto &i:a)cin>>i;
    IAOI_lib::dsu<int> d(n*m);
    for(int i=0;i<n;i++)
      for(int j=0;j<m;j++){
        if(i&&a[i-1][j]==a[i][j])d.merge((i-1)*m+j,i*m+j);
        if(j&&a[i][j-1]==a[i][j])d.merge(i*m+j-1,i*m+j);
      } // 先把四联通的连起来
    vector r(n-1,string(m-1,'.'));
    for(int i=1;i<n;i++)
      for(int j=1;j<m;j++){
        if(a[i-1][j-1]==a[i][j]&&!d.same((i-1)*m+j-1,i*m+j))
          d.merge((i-1)*m+j-1,i*m+j),r[i-1][j-1]='\\';
        else if(a[i-1][j]==a[i][j-1]&&!d.same((i-1)*m+j,i*m+j-1))
          d.merge((i-1)*m+j,i*m+j-1),r[i-1][j-1]='/';
      } // 只要找到未连通的就连
    for(int i=0;i<n*m;i++)
      c+=d.leader(i)==i; // 计算连通块个数，判断是否合法
    if(cout<<"Case #"<<t<<": ";c==2){
      cout<<"POSSIBLE\n";
      for(auto i:r)cout<<i<<'\n';
    }
    else cout<<"IMPOSSIBLE\n";
  }
  return 0;
}