比赛场次 | 626 |
---|---|
比赛名称 | 并查集专题 |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2024-09-05 19:00:00 |
结束时间 | 2024-09-05 19:05:00 |
开放分组 | 全部用户 |
注释介绍 | 亲戚:模板题 食物链,银河英雄传说:带权并查集 oiwiki并查集应用:https://oi-wiki.org/topic/dsu-app/ 动物园:A 树:D 呜呜呜 :E Disruption:F |
题目名称 | 动物园 |
---|---|
输入输出 | happyzoo.in/out |
时间限制 | 1000 ms (1 s) |
内存限制 | 128 MiB |
测试点数 | 20 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|
小 Z 计划带妹子去逛动物园。动物园有n个区域,从1到n编号。第i个区域有$a_i$只动物。动物园里有m条道路,道路是无向的,每条道路连接两个区域,且动物园是连通的,每两个区域之间都有路径相连。
小 Z 为了哄妹子高兴,需要提前规划旅行路线。对于两个区域p和q(p ≠ q)间的任意一条简单路径,定义其高兴度为路径上经过的区域中最少的动物数量(包括区域p和区域q)。小 Z 自然希望高兴度越高越好,定义p、q(p ≠ q)间最大的高兴度为p 、 q间所有简单路径中高兴度的最大值,记作f(p,q),现在小 Z 想知道,对于动物园任意两点的f(p,q)总和是多少。
输入的第一行为两个整数n和m,第二行包含n个整数,表示每个区域动物的数量。
接下来的每行,每行包含两个数$x_i$和$y_i(x_i \neq y_i)$,表示区域$x_i$和$y_i$之间有一条道路。
输出包含一行,一个整数表示最大高兴度总和,即$\sum_{p,q}^{p \neq q}{f(p,q)}$。
4 5 40 20 30 40 1 2 2 3 1 3 2 4 3 4
300
f(1,2) = 20 f(1,3) = 30 f(1,4) = 30
f(2,1) = 20 f(2,3) = 20 f(2,4) = 20
f(3,1) = 30 f(3,2) = 20 f(3,4) = 30
f(4,1) = 30 f(4,2) = 20 f(4,3) = 30
综合为300
对于 10%的测试数据,满足2 ≤n≤ 10, n-1 ≤ m ≤ 20。
对于 30%的测试数据,满足2 ≤ n ≤ 200, n-1 ≤ m ≤ 1000。
对于 50%的测试数据,满足2 ≤ n ≤ 1000, n-1 ≤ m ≤ 20000。
对于 100%的测试数据,满足2 ≤ n ≤ 10^5, n-1 ≤ m ≤ 10^6,
0 ≤$a_i$ ≤ 100000,1 ≤ $x_i, y_i$ ≤ $n$,($x_i \neq y_i$),保证是连通图且没有重边