题目描述

难度分:$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$：

1. 如果$a[u] \geq x$，那直接把$u \rightarrow fa$这条边修复（$fa$为$u$的父节点），将$u$和$fa$缩成一个点，此时这个点有沥青$a[x]+a[fa]-x$吨。
2. 如果$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$条边）：

1. 如果遍历完以$u$为根的子树后，当前节点$u$满足$a[u] \geq x$，将$u \rightarrow fa$这条边直接顺序加到答案数组$ans$中。
2. 否则就将$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;
}