观光路线

题目描述

十月的北京总是那么的迷人，而其中最令人沉醉的当属京郊的红叶。香山、蟒山、百望山、妙峰山等都是这个季节里赏红叶的好去处。秋色正浓，学校打算组织同学们下周秋游，秋游的地点选在了京郊新建的森林公园。

森林公园共包含 $N$ 个景点，编号 $1 \sim N$，景点之间共有 $M$ 条双向道路，与每个景点连接的道路的数量都是偶数。公园的任意两个景点之间，总存在一条或多条观光路线。参观这些景点总能让人感到身心愉悦，因此，每参观一个新的景点，同学们就能得到相应的愉悦值，但愉悦值并不是固定不变的——如果一个景点是所有景点中第 $k$ 个被新参观的，那这个景点能够带给同学们的愉悦值就会减少 $k$；如果一个景点被参观了多次，那只有第一次能够令同学愉悦，第二次起，参观这个景点就不再令同学愉悦。当然，走路是非常辛苦的，每走一条道路，包括重复走的，同学们就会得到一个 $-1$ 的愉悦值。

现在，学校请你能帮忙设计一条观光路线，要求从 $1$ 号景点开始参观，并最终回到 $1$ 号景点，而每个景点都被至少参观一次，每条道路也被至少完整地行走一次。在此基础上，学校希望同学们能够获得的愉悦值的总和最大。

输入格式

第一行包括两个整数 $N$ 和 $M$，分别表示森林公园中的景点总数和道路总数。

第二行包括 $N$ 个整数 $h_i$，表示编号 $i$ 的景点初始能够让同学们获得的愉悦值。

接下来 $M$ 行，每行包括两个整数 $a_i$ 和 $b_i$，表示一条道路所连接的两个景点的编号。

注意：两个景点之间可能存在多条道路。

输出格式

第一行包括一个整数，表示按学校要求，同学们能够获得的愉悦值总和的最大值。

第二行包括若干个整数，描述你所设计的观光路线，其中第 $i$ 个整数表示路线中第 $i$ 个走到的景点，包括重复走到的。相邻整数之间使用一个空格隔开。这条观光路线，应与第一行所计算出的愉悦值总和的最大值相对应。如果存在多条观光路线，请输出路线长度最短的；如果仍然存在多条，请输出字典序最小的。

注意：对于两个整数序列 ${a_i}$ 和 ${b_i}$，如果存在下标 $k$ 使得 $a_k < b_k$，且对于所有下标 $i$，$1 ≤ i < k$，均满足 $a_i = b_i$，则 ${a_i}$ 的字典序小于 ${b_i}$。

样例 #1

样例输入 #1

6 7
1 7 4 10 20 5
2 4
1 5
2 1
4 5
3 6
1 6
1 3

样例输出 #1

19
1 2 4 5 1 3 6 1

提示

【输入输出样例说明】

• 首先参观 $1$ 号景点（第 $1$ 个新参观的景点），同学们获得愉悦值 $1 - 1 = 0$。
• 接着参观 $2$ 号景点（第 $2$ 个新参观的景点），同学们获得愉悦值 $7 - 2 = 5$。
• 接着参观 $4$ 号景点（第 $3$ 个新参观的景点），同学们获得愉悦值 $10 - 3 = 7$。
• 接着参观 $5$ 号景点（第 $4$ 个新参观的景点），同学们获得愉悦值 $20 - 4 = 16$。
• 接着回到 $1$ 号景点。
• 接着参观 $3$ 号景点（第 $5$ 个新参观的景点），同学们获得愉悦值 $4 - 5 = -1$。
• 接着参观 $6$ 号景点（第 $6$ 个新参观的景点），同学们获得愉悦值 $5 - 6 = -1$。
• 最后回到 $1$ 号景点。
• 期间共走了 $7$ 条道路，因此总愉悦值还应减去 $7$，即 $(0 + 5 + 7 + 16 - 1 - 1) - 7 = 19$。

【数据规模与约定】

对于 40% 的数据，$N = M$。

对于 60% 的数据，$0 ≤ M - N ≤ 6$。

对于 80% 的数据，$2 ≤ N ≤ 1000$。

对于 100% 的数据，$2 ≤ N, M ≤ 50000$，$0 ≤ h_i ≤ 1000000$。

题解

由于题目所给的图是具有欧拉回路的（偶数个连接的边），因此可以使用欧拉回路的性质解决这个问题。

首先计算愉悦值的总和。根据题意，同学们参观每个景点都会得到一个愉悦值，而重复参观相同的景点不会再次增加愉悦值，因此最终的愉悦值总和为每个景点的初始愉悦值减去该景点在整个参观过程中被新参观的次数。

接下来，我们需要找到一条包括所有景点和道路的观光路线。由于图是具有欧拉回路的，我们可以使用深度优先搜索（DFS）来构建观光路线。

具体做法如下：

1. 首先，对于每个景点，将与之相连的道路按照连接的景点的愉悦值进行排序。这样做的目的是为了保证在构建观光路线时，能够优先选择愉悦值较大的景点。
2. 从起点景点（编号为1）开始进行DFS搜索，选择与当前景点相连的道路中未访问过的道路，并将其标记为已访问。在DFS的过程中，我们将访问过的景点按照访问的顺序依次压入一个栈中。
3. 当栈为空时，表示所有的景点都已经访问过，并且构建了观光路线。此时，按照栈中的顺序输出景点的编号即可。

最后，输出愉悦值总和和观光路线。

代码如下：

#include <bits/stdc++.h>

#define int long long
#define setp setprecision
#define mem(a, m) memset(a, m, sizeof(a))
using namespace std;

const int INF = 0x3f3f3f3f;
int n, m;
struct node
{
    int v, id;
};
int h; // 声明一个变量h
vector<node> e[50005]; // 定义一个大小为50005的node类型的vector数组e，用于存储图的边
stack<int> ans; // 定义一个栈ans，用于存储深度优先搜索的结果
bool vis[50005]; // 定义一个bool类型的数组vis，用于记录边的访问情况
int s = 0; // 声明一个变量s，初始化为0
void dfs(int u) // 深度优先搜索函数，参数为当前搜索的节点编号u
{
    for (int i = 0; i < e[u].size(); i++) // 遍历节点u的所有邻接节点
    {
        int v = e[u][i].v, id = e[u][i].id; // 获取当前邻接节点的编号v和边的编号id
        if (vis[id]) // 如果当前边已经被访问过，则跳过该边
            continue;
        vis[id] = 1; // 将当前边标记为已访问
        dfs(v); // 递归搜索邻接节点v
    }
    ans.push(u); // 将当前节点u压入栈中
}
int cmp(node a, node b) // 自定义的比较函数，用于排序边的邻接节点
{
    return a.v < b.v; // 按照节点编号v的升序进行排序
}
signed main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m; // 输入节点数n和边数m
    for (int i = 1; i <= n; i++)
        cin >> h, s += h - i; // 循环读取每个节点的高度h，并计算s+=h-i的累加值
    for (int i = 1; i <= m; i++) // 循环读取每条边的两个节点编号
    {
        int a, b;
        cin >> a >> b;
        e[a].push_back((node){b, i}); // 将边(a,b)插入节点a的邻接表中
        e[b].push_back((node){a, i}); // 将边(b,a)插入节点b的邻接表中
    }
    cout << s - m << endl; // 输出s-m的结果
    for (int i = 1; i <= n; i++)
        if (!e[i].empty())
            sort(e[i].begin(), e[i].end(), cmp); // 对每个节点的邻接边按照邻接节点编号进行排序
    dfs(1); // 从节点1开始进行深度优先搜索
    while (!ans.empty()) // 输出深度优先搜索的结果
        cout << ans.top() << " ", ans.pop();
    return 0;
}