题解 P5049 【旅行(数据加强版)】

2018-11-26 09:22:40


我们选择n方过百万

树的情况很容易解决,一直往编号小的子节点DFS下去就行了。

m=n 也就是带有一个环。这里我们考虑拆边解决

冷静分析一波,我们发现:初始状态下,从一个点走向环上的一个点存在至多两种方法。换言之,我们在不断取最小儿子向下走时可以放弃当前子树回溯一次

显然,上述放弃子树反悔祖先是有一定条件的。例如,下图所示情况不能返回祖先,否则当前点的子树将永远无法到达。

再如下图,当前点的子树是环(或子树中有环)也不能立即回溯。

这样也不行呢qwq

看来只有这样子才可以暂时放弃子树回溯了:(也就是当前点和当前点的子结点都在环上,当前点的父亲也在环上)

当然,满足可回溯条件时我们并不会马上无脑回溯,而会先考虑回溯能否使解变得更优。这个其实很简单,看看未遍历的祖先(及其儿子)中最小的一个是否小于当前点的决策,这条信息在DFS时传递下去即可。

放弃子树的回溯只能用一次qwq


#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 500005
#define maxe (maxn << 1)

using namespace std;

int n, m, stck[maxn], top, cir = 1, in[maxn], cnt;
int ans[maxn], to[maxn << 2], s[maxn], idx = 0, len = 0;
int lnk[maxn], nxt[maxe], son[maxe], tot = 1;
bool vis[maxn], flg[maxn];
int num = 0;

inline int read()
{
    char ch = getchar();
    int ret = 0, f = 1;
    while (ch > '9' || ch < '0')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        ret = ret * 10 + ch - '0', ch = getchar();
    return ret * f;
}

void adde(int x, int y)
{
    son[++tot] = y, nxt[tot] = lnk[x], lnk[x] = tot;
}

void Trump()
{
    memset(flg, 1, sizeof(flg));
    for (int i = 1; i <= n; ++i)
        flg[i] = true;
    top = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (in[i] == 1)
            stck[++top] = i;
    }
    while (top)
    {
        int now = stck[top--];
        flg[now] = 0, cnt--;
        for (int j = lnk[now]; j; j = nxt[j])
        {
            in[son[j]]--;
            if (in[son[j]] == 1)
                stck[++top] = son[j];
        }
    }
}

void DFS(int now, int lst, int pre)
{
    if (!vis[now])
    {
        ans[++idx] = now;
        if (flg[now])
            cnt--;
    }
    vis[now] = 1;
    int l = len + 1, r = len;
    for (int j = lnk[now]; j; j = nxt[j])
    {
        if (!vis[son[j]])
            to[++len] = son[j];
    }
    if (len < l)
        return;
    r = len, len++;
    sort(to + l, to + 1 + r);
    if (s[now] == 0)
        s[now] = 1;
    for (s[now] = l; s[now] <= r; ++s[now])
    {
        if (s[now] == r)
        {
            if (flg[to[s[now]]] && flg[now] && flg[pre]
                    && to[s[now]] > lst && cir < 0)
            {
                cir = 1;
                return;
            }
            DFS(to[s[now]], lst, now);
        }
        else
            DFS(to[s[now]], to[s[now] + 1], now);
    }
}

int main()
{
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
    n = read(), m = read();
    memset(s, 0, sizeof(s));
    for (int i = 1; i <= m; ++i)
    {
        int x = read(), y = read();
        adde(x, y), adde(y, x);
        in[x]++, in[y]++;
    }
    if (n == m)
    {
        cir = -1, cnt = n;
        Trump();
        flg[0] = true;
    }
    DFS(1, n + 1, 0);
    for (int i = 1; i <= n; ++i)
        printf("%d ", ans[i]);
    return 0;
}

NOIp的时候脑残,用环上挂着的链来判回溯条件,炸掉3个点QAQ