[CF1804E] Routing 题解

· · 题解

@Departure_ 这么强！！！！！

拿样例来研究一下，容易发现这个 a(u) 的钦定实际上可以看作一条边，于是在原图上提出了一个内向基环森林，然后在这个森林上的每一个点在走若干步后一定能到达任意点的邻居。

首先每棵树的环外点深度可以控制在 1，因为如果有深度大于 1 的，说明深度大于 1 的每个点都与环上点有边相连，可以调整至直接相连。然后这个森林应该是一棵树，因为一个森林合法说明任意一个环上的任意一个点都与其他每个环上的至少一个点有边相连，于是这个环上的所有点就都可以成为其他树的环外点。

于是我们得到了一个很简洁的性质：(u,a(u)) 构成的图为一颗基环树，且环上点直接连接了所有其他点。形式化地，设 G_i 表示与 i 相连的点集，若 S 为环上的点集，则有 \bigcup_{u\in S}G_u=V，其中 V 为所有点构成的集合。

然后怎么找环呢？可以考虑先找到一个链，一个朴素的想法是设 f_{S,i,j} 表示当前链上点集为 S，链首为 i，链末为 j 是否可行，复杂度显然不对。注意到环的对称性，可以钦定 S 中编号最小的点为链首。然后发现每个状态只对应一个 0/1 太浪费了，可以把 f_{S,j} 压成一个集合，于是变为 f_{S} 表示链首为 \text{lowbit}(S)，此时可行的链尾集合是什么。然后转移大概是 i\to f_{S\cup\{i\}}(f_S\cap G_i\neq \varnothing)。注意到 f_S 的答案实际上就记录了其前驱，所以可以直接找。

时间复杂度 \mathcal{O}(n2^n)。

::::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define pob pop_back
using namespace std;
typedef long long ll;
const ll N=20,p=1e9+7,ee=1e18;
ll n,m,G[N+5],f[1<<N],ans[N+5];
ll _(ll x){return (1<<(x-1));}
void check(ll S){
    ll u=0,cur,T;
    for(ll i=1;i<=n;i++)if(S>>(i-1)&1){u=i; break;}
    cur=G[u]&f[S];
    if(!cur) return;
    for(ll i=1;i<=n;i++) ans[i]=0;
    T=S;
    for(ll v,lst=u;;){
        if(!cur) return;
        v=__lg(cur&(-cur))+1,ans[v]=lst,S^=_(v);
        if(S==_(u)){ans[u]=v; break;}
        cur=(f[S]&G[v]),lst=v;
    }
    cout<<"Yes\n";
    for(ll i=1;i<=n;i++)if(T>>(i-1)&1){
        for(ll j=1;j<=n;j++){
            if(ans[j]) continue;
            if(G[i]>>(j-1)&1) ans[j]=i;
        }
    }
    for(ll i=1;i<=n;i++) cout<<ans[i]<<" "; cout<<"\n";
    exit(0);
}
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(ll i=1,u,v;i<=m;i++){
        cin>>u>>v;
        G[u]|=_(v),G[v]|=_(u);
        if(u>v) swap(u,v);
        f[_(u)|_(v)]=_(v);
    }
    for(ll i=1;i<=n;i++) G[i]|=_(i);
    for(ll S=0,val;S<(1<<n);S++)if(f[S]){
        val=0;
        for(ll i=1;i<=n;i++){
            if(S>>(i-1)&1){
                val|=G[i];
                continue;
            }
            if(__lg(S&(-S))+1>=i) continue;
            if(f[S]&G[i]) f[S|_(i)]|=_(i);
        }
        if(val==(1<<n)-1) check(S);
    }
    cout<<"No\n";
    return 0;
}

::::