题目描述
难度分:$2600$
输入$n(2 \leq n \leq 3 \times 10^5)$,$m(n-1 \leq m \leq 3 \times 10^5)$,$ x(1 \leq x \leq 10^9)$,表示一个$n$点$m$边的无向图(节点编号从$1$开始)。
输入长为$n$的数组$a(0 \leq a[i] \leq 10^9)$,表示每个点的点权。
然后输入$m$条边。保证图中没有自环和重边。保证图是连通的。
把点视作城市,把边视作道路。一场地震摧毁了所有的道路,现在需要修复其中$n-1$ 条道路,将所有城市连接起来。
城市$i$有$a[i]$吨沥青。如果城市$i$和城市$j$的沥青总量至少是$x$,那么可以修复$i$和$j$之间的道路,并消耗$x$吨沥青。
一个城市的沥青可以沿着修好的道路运往其它城市。是否可以将所有城市连接起来?
如果不能,输出NO
。如果能,输出YES
,并按照修路的顺序,依次输出这$n-1$ 条边的编号(输入的第$i$条边的编号是$i$,从$1$开始)。如果有多种方案,输出任意一种。
输入样例$1$
5 4 1
0 0 0 4 0
1 2
2 3
3 4
4 5
输出样例$1$
YES
3
2
1
4
输入样例$2$
2 1 2
1 1
1 2
输出样例$2$
YES
1
输入样例$3$
2 1 2
0 1
1 2
输出样例$3$
NO
输入样例$4$
5 6 5
0 9 4 0 10
1 2
1 3
2 3
3 4
1 4
4 5
输出样例$4$
YES
6
4
1
2
算法
Kruskal
算法+DFS
先看看什么时候是无解的,可以发现,当$\Sigma_{i=1}^{n}a[i] \lt x \times (n-1)$时,所有城市的沥青加起来都不够连接$n-1$条道路,此时肯定无解。
证明一下其他情况下肯定有解,对于一个叶子节点$u$:
- 如果$a[u] \geq x$,那直接把$u \rightarrow fa$这条边修复($fa$为$u$的父节点),将$u$和$fa$缩成一个点,此时这个点有沥青$a[x]+a[fa]-x$吨。
- 如果$a[u] \lt x$,把$u$“删除”,此时还剩下$n-1$个节点,由于$a[u] \lt x$,那剩下的节点就满足沥青总量$\geq x \times (n-2)$。按照归纳假设,剩下的节点就可以连成一棵树,那么剩余的沥青就都能为修复$u \rightarrow$这条边所用(可以运过来),而沥青的总量$\Sigma_{i=1}^{n}a[i] \geq x \times (n-1)$,因此这条边也肯定能修复。因此一旦$a[u] \lt x$,那$u \rightarrow fa$这条边就最后再修复。
利用Kruskal
算法选出一棵生成树,然后考虑如何将这棵树上的边都修复。不妨以$1$为根节点进行DFS
,申请一个长度为$n-1$的答案数组$ans$(反正有解的话答案就是$n-1$条边):
- 如果遍历完以$u$为根的子树后,当前节点$u$满足$a[u] \geq x$,将$u \rightarrow fa$这条边直接顺序加到答案数组$ans$中。
- 否则就将$u \rightarrow fa$这条边倒着插入到答案数组$ans$中,表示这条边最后才选。越远离根节点、满足$a[u] \lt x$的节点$u$,其对应的边$u \rightarrow fa$就越后选。
注意在这个DFS
的过程中,一边修复道路,需要动态更新$a[u]$的值。DFS
完成后顺序输出$ans$数组中边的编号即可,实现有一些细节,详见代码。
复杂度分析
时间复杂度
Kruskal
选出生成树的时间复杂度为$O(mlogm)$,其中$O(logm)$是合并节点时的操作,$O(m)$是遍历边集的时间复杂度。接下来对整个图进行DFS
,需要遍历到所有选到的$n-1$条边和$n$个节点,且不会重复遍历,因此时间复杂度是$O(n)$。综上,整个算法的时间复杂度是$O(mlogm+n)$。
空间复杂度
除去输入的点权数组$a$和输出的答案数组$ans$,并查集的父节点数组$p$的空间复杂度为$O(n)$,生成树的邻接表空间消耗是节点数+边数,为$n+n-1$,仍然是$O(n)$级别的。综上,整个算法的额外空间复杂度为$O(n)$。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <array>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 300010;
int n, m, x, p[N], ans[N], cnt1, cnt2;
LL tot, a[N];
vector<array<int, 2>> graph[N];
int find(int x) {
return p[x] == x? x: p[x] = find(p[x]);
}
void merge(int x, int y) {
int rx = find(x), ry = find(y);
if(rx != ry) {
p[rx] = ry;
}
}
bool is_connected(int x, int y) {
return find(x) == find(y);
}
// fa通过ei这条边到u
void dfs(int u, int fa, int ei) {
for(auto&tup: graph[u]) {
int v = tup[0];
if(v == fa) continue;
dfs(v, u, tup[1]);
}
if(u == 1) return;
if(a[u] >= x) {
// 连接u和fa
a[fa] += a[u] - x;
ans[++cnt1] = ei;
}else {
ans[--cnt2] = ei;
}
}
int main() {
scanf("%d%d%d", &n, &m, &x);
cnt1 = 0;
cnt2 = n;
tot = 0;
for(int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
p[i] = i;
tot += a[i];
}
vector<array<int, 2>> edges;
for(int i = 0; i < m; i++) {
int x, y;
scanf("%d%d", &x, &y);
edges.push_back({x, y});
if(is_connected(edges[i][0], edges[i][1])) continue;
merge(edges[i][0], edges[i][1]);
graph[edges[i][0]].push_back({edges[i][1], i + 1});
graph[edges[i][1]].push_back({edges[i][0], i + 1});
}
// 无解
if(tot < (n - 1LL)*x) {
puts("NO");
exit(0);
}
// 有解
puts("YES");
dfs(1, 0, 0);
for(int i = 1; i < n; i++) {
printf("%d\n", ans[i]);
}
return 0;
}