旺崽的博客

要么天赋异禀，要么天道酬勤

0%

2021牛客寒假算法基础集训营3 G.糖果

发表于 分类于 Valine：

2021牛客寒假算法基础集训营3 G.糖果

题目链接

题目描述

在一个幼儿园里面有 $\mathit n$ 个小朋友，分别编号 $\text 1,2,…,n$。在这些小朋友中有一些小朋友互为朋友关系，总共有 $\mathit m$ 对朋友。
作为幼儿园老师，你想买一些糖果分给小朋友，你知道第 $\mathit i$ 个小朋友想要至少 $a_{i}$ 个糖果，否则他就会不开心。
同时，如果一个小朋友得到的糖果数小于他某个朋友得到的糖果数，他也会不开心。
请问你最少买多少糖果才能保证每个小朋友都不会不开心呢？

输入描述:

第一行以空格分隔的两个整数 $\mathit n,m$。
第二行以空格分隔的 $\mathit n$ 个正整数 $a{i}$。
接下来 $\mathit m$ 行每行以空格分隔的两个正整数 $\mathit u,v$u,v，代表 $\mathit u$ 是 $\mathit v$ 的朋友，$\mathit v$ 是 $\mathit u$ 的朋友。
$1\leq n\leq 10^{6}$
$0\leq m\leq 10^{6}$
$1\leq a{i} \leq 10^{9}$
$1\leq u,v \leq n,u≠v$

输出描述:

购买的最少糖果数以保证每个小朋友都不会不开心。

示例1

输入

1
2
3
3 1
1 2 3
1 2

输出

1
7

DFS~
显然我们可以根据朋友关系把图分成很多个连通块，在每一个连通块中，可以求出连通块中元素的数量 $cnt$ 和最大糖果数量 $a$，则最后的答案即为：

AC代码如下：

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
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int n, m, u, v, vis[N];
vector<int> G[N];
ll ans, cnt, mx, a[N];

void dfs(int x) {
    vis[x] = 1;
    cnt++;
    mx = max(mx, a[x]);
    for (auto y:G[x]) {
        if (!vis[y]) dfs(y);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    while (m--) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            cnt = mx = 0;
            dfs(i);
            ans += cnt * mx;
        }
    }
    printf("%lld", ans);
    return 0;
}