CF1804E Routing

· · 题解

RMJ 真的完蛋了……

题意

给定一个 n 个点 m 条边的 无向联通图，称 y 是 x 的邻居，当且仅当无向边 (x,y) 存在。

你需要构造一个序列 (a_1,\dots,a_n)，满足：

或报告无解。

分析

首先转换题意，可以按照给的方式构造一个基环树，且环上挂的树高最多为 1，那也就是说从原图上抓一颗基环树下来，且环外的每个点都直接想换连边。

看到数据范围 n\leq20 激动了，直接暴力枚举环是哪一个集合不就结束了！结果发现不会通过集合构造对应的环……

仔细思考了一下，感觉是很套路的 dp。直接找环可能有困难，所以我们考虑先找一条链，在把首位接上。直接设 f_{S,i} 表示选的集合为 S，起点是 i，可能的终点集合。仔细一想，这是一个环耶，那我们把上面每一个点都当起点算一遍不是很傻，所以直接设 \min(S) 为起点，这样就可以省掉一维了！

找答案可以直接每次枚举可能终点，让后从他下一个点连过来。

总复杂度 \mathcal O(n2^n)，随便跑。

code

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define LL long long
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
#define FileIO(ch) freopen(ch".in", "r", stdin), freopen(ch".out", "w", stdout)
using namespace std;

namespace IO {
    char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
    inline long long read() {
        char ch = gh();
        long long x = 0;
        bool t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? ~(x - 1) : x;
    }
    template <typename _Tp>
    inline void write(_Tp x) {
        static char stk[64], *top = stk;
        if (x < 0) {
            x = ~(x - 1);
            putchar('-');
        }
        do *top++ = x % 10, x /= 10;
        while (x);
        while (top != stk) putchar((*--top) | 48);  
    }
}

using IO::read;
using IO::write;

const int maxn(25), maxb((1 << 20) + 7);
int n, m, g[maxn], f[maxb], p[maxn];

inline int lowbit (int x) { return x & (-x); }

int main() {
    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read();
        g[u] |= 1 << v - 1;
        g[v] |= 1 << u - 1;
    }
    for (int i = 1; i <= n; i++) f[1 << i - 1] = 1 << i - 1;
    for (int s = 0; s < (1 << n); s++) {
        if (__builtin_popcount(s) < 2) continue;
        for (int i = 1; i <= n; i++) {
            if (s >> i - 1 & 1) {
                if ((1 << i - 1) == lowbit(s)) continue;
                if (f[s ^ (1 << i - 1)] & g[i]) f[s] |= (1 << i - 1);
            }
        }
    }
    for (int s = 0; s < (1 << n); s++) {
        bool flg = 1;
        int x = __lg(lowbit(s)) + 1;
        if (!(f[s] & g[x])) continue;
        for (int i = 1; i <= n; i++) {
            if (s >> i - 1 & 1) continue;
            if (!(g[i] & s)) { flg = 0; break; }
        }
        if (!flg) continue;
        for (int i = 1; i <= n; i++) if (!(s >> i - 1 & 1)) p[i] = __lg(lowbit(s & g[i])) + 1;
        int t = s;
        while (t) {
            for (int i = 1; i <= n; i++) if ((f[t] >> i - 1 & 1) && (g[x] >> i - 1 & 1)) {
                p[x] = i, t ^= (1 << i - 1), x = i;
                break;
            }
        }
        break;
    }
    if (!p[1]) return puts("No");
    puts("Yes");
    for (int i = 1; i <= n; i++) writesp(p[i]);
}
// I love WHQ!