顺序 - 代码源竞赛平台

题目描述

一套控制系统中有 $n$ 台设备，编号为 $1$ 至 $n$ 。其中有 $m$ 对设备通过双向线路直接相连。每台设备 $i$ 的初始读数为非负整数 $a_i$ 。

你需要给这些设备安排一个调节顺序 $p_1,p_2,\ldots,p_n$ ，使每台设备恰好调节一次。调节设备 $u$ 时，它的读数会变为自己与所有直接相连设备的当前读数中的最小值，其他设备的读数不变。没有直接相连设备时，它的读数不变。

请让全部调节结束后所有设备的读数之和尽可能大，并在达到最大总和的所有调节顺序中，找出字典序最小的一个。

这里的调节顺序是 $1,2,\ldots,n$ 的一个排列。比较两个不同顺序的字典序时，找到第一处编号不同的位置，该位置编号较小的顺序字典序较小。

线路构成一张无向简单图，可以不连通：一台设备不能与自己相连，任意两台设备之间至多有一条线路。

输入格式

第一行包含一个正整数 $n$ 和一个非负整数 $m$ ，分别为设备的数量和线路的数量。

第二行包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$ ，其中 $a_i$ 为设备 $i$ 的初始读数。

接下来 $m$ 行，每行包含两个正整数 $u_i,v_i$ ，表示设备 $u_i$ 与设备 $v_i$ 之间有一条线路。

输出格式

第一行输出一个非负整数，表示全部调节结束后所有设备读数之和的最大值。

第二行输出 $n$ 个正整数 $p_1,p_2,\ldots,p_n$ ，表示所有达到最大总和的调节顺序中字典序最小的一个。

若只求出了最大总和，可以只输出第一行，按照下方规则获得部分分。

样例

4
1 3 2

15
2 3 4 1

样例解释

样例 1：按 $1,3,2$ 的顺序调节，最终读数为 $(1,1,2)$ ，总和为 $4$ 。按 $1,2,3$ 的顺序调节会得到 $(1,1,1)$ ，不能达到最大总和。

样例 2：先依次调节设备 $2,3,4$ ，它们的读数均不变；最后调节设备 $1$ ，其读数变为 $1$ 。最终总和为 $1+1+5+8=15$ 。

数据规模

本题各子任务单独计分。须通过某子任务包含的所有测试点，方可获得该子任务的分数。

每个子任务的分数分为相等的两部分：该子任务所有测试点的第一行输出均正确，可获得一半分数；该子任务所有测试点的两行输出均满足要求，可再获得另一半分数。第二部分未通过时，不影响已经获得的第一部分分数。

子任务编号	分数	$n\le$	特殊性质
$1$	$20$	$8$	无
$2$	$30$	$2000$	无
$3$	$10$	$2\times10^5$	特殊性质 A
$4$	$40$	$2\times10^5$	无

特殊性质 A：所有设备的初始读数相等，即 $a_1=a_2=\cdots=a_n$ 。

对于 $100\%$ 的数据， $1\le n\le2\times10^5$ ， $0\le m\le\min(2\times10^5,\frac{n(n-1)}{2})$ ， $0\le a_i\le10^9$ ， $1\le u_i,v_i\le n$ ， $u_i\ne v_i$ 。图中没有重边，不保证连通。