Phoenix and Earthquake | Codeforces 1515F

发表于 分类于 本文字数： 1.3k 阅读时长 ≈ 1 分钟

题目链接

给定一张 \(n\) 个点 \(m\) 条边的无向连通图和正整数 \(x\)，点有非负权值 \(a_i\)。

如果一条边 \((u,v)\) 满足 \(a_u+a_v \ge x\)，可以将 \(u,v\) 缩起来，新点的点权为 \(a_u+a_v-x\)。

判断这张图是否可以缩成一个点并给出方案。

\(n,m \le 3 \cdot 10^5,x,a_i \le 10^9\)

首先将每个点的点权减去 \(x\)，则合并条件变为 \(a_u + a_v \ge -x\)，每次合并后新点的点权为 \(a_u + a_v\)。

结论：这张图可以缩成一个点的充要条件是点权和大于等于 \(-x\)。

必要性显然，充分性可以考虑这个构造：每次选择点权最大的点 \(u\) 的任意一条边。

构造的正确性可以考虑反证法，设这条边为 \((u,v)\)，假设这条边不行，即 \(a_u+a_v<-x\)。

进一步 \(\because a_v \ge -x,\therefore a_u < 0\)

由于 \(a_u\) 是最大值，因此所有点的点权都是负数，那么 \(a_u+a_v \ge \sum a_i \ge -x\)，推出矛盾！

至此，已经得到一个做法。

但还有更简单的做法，根据上面结论，任意求一棵生成树都有可行方案。

先从叶子向根依次考虑每个结点，如果这个结点权值非负，则选择它和它父亲的连边，再从根向叶子依次考虑每个结点，如果它和它父亲的连边还没选，则选择这条边。

证明考虑数学归纳法即可。

在实现中不必 DFS 两遍，DFS 过程中把没选的边压栈即可。

复杂度 \(O(n)\)。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define eb emplace_back

using namespace std;

const int N = 3e5 + 5;

int n, m, x, vis[N], as[N], L, R;
long long a[N], su;
vector <pair <int, int>> G[N];

void dfs(int u) {
    vis[u] = 1;
    for(auto [v, i] : G[u]) if(!vis[v])
        dfs(v), a[v] >= 0 ? a[u] += a[v], as[L++] = i : as[R--] = i;
}
int main() {
    cin >> n >> m >> x;
    rep(i, 1, n) scanf("%lld", &a[i]), su += a[i] -= x;
    int u, v;
    rep(i, 1, m) scanf("%d%d", &u, &v), G[u].eb(v, i), G[v].eb(u, i);
    if(su + x < 0) puts("NO"), exit(0);
    puts("YES"), L = 2, R = n, dfs(1);
    rep(i, 2, n) printf("%d\n", as[i]);
    return 0;
}