题解 P5022 【旅行】

· · 题解

深搜+剪枝+氧气优化 全点100ms以内

然而本蒟蒻考场上并没有做出来emm

根据良心数据规模可以看出来这张图要么是一棵树，要么就是多了一条边的树（雾

所以我们就可以想办法让不是树的图变成树。

于是就可以考虑到暴力删边。

暴力删边的方法上面神犇们的题解都应该讲过了，这里不再赘述，主要说说我剪枝的方法。

其实这个方法并不是很好，但是不加的话最后三个点妥妥T飞，实现起来也很容易。 那就是把当前的答案数组记录下来，并和之前生成的字典序最小的答案进行比较。只要在搜索的过程中发现字典序比先前生成的最小的答案大，就直接return。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
const int INF = 2140000000;
int bana, banb;
bool control = false;

struct map
{
    int c;
    int nxt;
    bool used;
}e[2*5010];//一定要开两倍，因为存了双向边
int head[5010];
bool visited[5010];
int minans[5010];//即最小字典序
int ans[5010];//即当前搜索的字典序
int cntans = 0, maxcntans = 0;
int cnt = 0;

void read(int x, int y) //前向星存边
{
    cnt++;
    e[cnt].c = y;
    e[cnt].nxt = head[x];
    head[x] = cnt;
}
int n, m;

bool larger() //比较ans是否大于minans
{
    for (int i = 1; i <= cntans; i++)
    {
        if (ans[i] > minans[i])
            return true;
        if (ans[i] < minans[i])
            return false;
    }
    return false;
}

void dfs(int sur)
{
    visited[sur] = true;
    ans[++cntans] = sur;
    if (control&&cntans <= maxcntans && larger())//这就是上面讲过的剪枝
        return;
    priority_queue <int, vector<int>, greater<int> >q;
    for (int i = head[sur]; i; i = e[i].nxt)
    {
        if (visited[e[i].c]||(e[i].c==banb&&sur==bana)|| (e[i].c == bana && sur == banb))
            continue;
        q.push(e[i].c);
    }
    while (!q.empty())
    {
        dfs(q.top());
        q.pop();
    }
}//用优先队列保存每一个根节点的子节点，按数字从小到大进行深搜
//其实这里有贪心的思想，每次取当前最优解，就得到全局最优解

int main()
{
    int x, y;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &x, &y);
        read(x, y);
        read(y, x);
    }
    int sur = 1;
    if (m == n - 1)
    {
        //是树的情况
        cntans = 0;
        bana = -1;
        banb = -1;
        dfs(sur);
        for (int i = 1; i <= cntans; i++)
            printf("%d ",ans[i]);
    }
    else
    {
        //不是树的情况
        control = true;
        for (int i = 1; i <= 2*m; i+=2)
        {
            memset(visited, 0, sizeof(visited));
            cntans = 0;
            bana = e[i+1].c;
            banb = e[i].c;//选出删除的边（这里选出的是这条边连接的两个结点
            dfs(sur);
            if (cntans > maxcntans || (cntans >= maxcntans && !larger()))
            {
                memcpy(minans, ans, sizeof(ans));//复制ans到minans
                maxcntans = cntans;
            }
        }
        for (int i = 1; i <= maxcntans; i++)
            printf("%d ",minans[i]);
    }
    return 0;
}