P13537 题解

· · 题解

不难发现一个图有解当且仅当它联通。

一个朴素的想法是，把最终的结果按照列分割成若干块，每块宽 3 格，两边全部放同一种颜色 x，中间放与 x 相邻的颜色。

当然为了确保相邻块的 x 之间有连边，需要找一棵生成树并在必要的时候回溯。为了方便实现，使用 dfs 生成树。

这个做法可以做到 4n。

现在我们保留生成树，递归地构造答案。如果生成树上一个点 x 有多个儿子，那么是说，这个点是子树中所有点导出子图的一个割点，删掉之后导出子图变成多个联通块。

用 x 将它的不同子树分隔开来，有如下构造：

xxxxxxxxx
x1x2x3x4x
xxxxxxxxx
x...x...x
x...x...x
x...x...x
x...x...x

其中两个 . 的连通块代表 x 的不同子树，数字代表子树中与 x 有边相连的点。

显然这个构造可以做到宽度 2n-1，长度 3n，尝试进一步优化。

为了保证构造中 1234 的位置不和其他东西相邻，需要把与它直接相邻的位置填上 x，因而可以挖掉角上的位置得到

_x_x_x_x_
x1x2x3x4x
xx.xxx.xx
x...x...x
x...x...x
x...x...x
x...x...x

或者

x_x_x_x_x
xx1x2x3xx
x.x.x.x.x
x...x...x
x...x...x
x...x...x
x...x...x

其中 _ 为上一层用掉的部分。

相邻层之间交错排列，这样就可以做到 2n+1。发现最外面一层的数字上面不需要放东西，可以再省掉一层，做到 2n。

显然如果一个子树大小为 s>1，那么按照这种构造，上面一层至少会留下 s-2 个位置可以用来填数。子树内至多有 s-1 个与 x 相邻的点，其中又有至少一个是它的儿子，因此 s-2 个是够用的。

#include<bits/stdc++.h>
using namespace std;
#define ll int
const ll N=250;
int n,m,k,ans[N][N],ok[N],vis[N],TO[N][N];
vector<int> to[N];
void dfs(int u){
    vis[u]=1;
    for (auto v:to[u]) if (ok[v]&&vis[v]==0) dfs(v);
}
void del(vector<int>& vec,int x){
    if (vec.size()==0) return;
    for (int i=0;i<vec.size();++i) if (vec[i]==x){
        swap(vec[i],vec.back());break;
    }
    if (vec.back()==x) vec.pop_back();
}
void solve(vector<int> vec,int l,int r,int h){
    assert(vec.size());assert(r-l==(vec.size()-1)*2);
    int u=vec[0];
    if (vec.size()==1){
        for (int i=1;i<=h;++i) for (int j=l;j<=r;++j) ans[i][j]=u;
        for (int i=l;i<=r;++i) if (ans[h+1][i]==0) ans[h+1][i]=u;
        return;
    }
    for (auto x:vec) ok[x]=1;
    dfs(u);
    for (auto x:vec) assert(vis[x]);
    for (auto x:vec) vis[x]=0;
    for (int i=1;i<=h;++i) ans[i][l]=ans[i][r]=u;
    for (int i=l;i<=r;++i) ans[h][i]=u;
    if (ans[h+1][l]==0) ans[h+1][l]=u;
    if (ans[h+1][r]==0) ans[h+1][r]=u;
    int d=l+1+(ans[h+1][l+1]!=0);
    for (auto x:to[u]) if (ok[x]){
        assert(d<r);
        assert(ans[h+1][d]==0);
        ans[h+1][d]=ans[h-1][d]=u;
        ans[h][d]=x;
        d+=2;
    }
    while(d<r){
        assert(ans[h+1][d]==0);
        ans[h+1][d]=ans[h][d]=ans[h-1][d]=u;
        d+=2;
    }
    d=l;
    for (int i=1;i<=n;++i) ok[i]=0;
    del(vec,u);
    while(vec.size()){
        int v=0;
        for (auto x:vec) if (TO[u][x]){v=x;break;}
        assert(v);
        vector<int> nxt(1,v);
        for (auto x:vec) ok[x]=1;
        dfs(v);
        for (auto x:vec) if (vis[x]&&x!=v) nxt.emplace_back(x);
        for (auto x:nxt) del(vec,x);
        solve(nxt,d+1,d+2*nxt.size()-1,h-2);
        d+=2*nxt.size();
        for (int i=1;i<=h;++i) ans[i][d]=u;
        for (int i=1;i<=n;++i) ok[i]=vis[i]=0;
    }
    assert(d==r);
}
vector<vector<int> > create_map(int N,int M,vector<int> A,vector<int> B){
    memset(ans,0,sizeof(ans));
    n=N;m=M;
    for (int i=0;i<m;++i){
        to[A[i]].emplace_back(B[i]);
        to[B[i]].emplace_back(A[i]);
        TO[A[i]][B[i]]=TO[B[i]][A[i]]=1;
    }
    m=0;k=2*n;
    vector<int> vec;
    for (int i=1;i<=n;++i) vec.emplace_back(i);
    solve(vec,1,k-1,k);
    vec.clear();
    for (int i=1;i<=n;++i) to[i].clear();
    for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) TO[i][j]=0;
    for (int i=1;i<=k;++i) ans[i][k]=ans[i][k-1];
    vector<vector<int> > ans(k,vector<int>(k,0));
    for (int i=1;i<=k;++i) for (int j=1;j<=k;++j) ans[i-1][j-1]=::ans[i][j];
    return ans;
}