解题思路
本题是无向图连通块 + 块内统计,可按以下步骤处理:
- 特判:若
edges 为空(M=0),不存在节点数 ≥2 的供电区,直接返回 −1。
- 并查集/DFS:根据
edges 将节点划分为若干连通块(供电区)。
- 块内计算:对每个节点数 ≥2 的连通块,取块内
loads 的最大值、最小值,计算
不均衡度=(max−min)×∣块∣。
- 取最大:在所有有效连通块的不均衡度中取最大值;M>0 时至少存在一个有效块。
P14399.分析电网负载均衡(200分)
题目内容
某电力公司管理N个变电站节点(编号0~N-1),节点间通过M条输电线路连接,相连节点属于同一供电区。定义供电区的不均衡度=区内最大负载与最小负载之差 ×节点数。请找出不均衡度最大的供电区,输出其不均衡度。若无有效供电区(节点数<2或M=0),输出-1。
输入描述
整型数组loads,长度为N,表示编号0~N-1的节点负载(MW);
二维整型数组edges,每行2个整数,表示该线路连接的两个节点编号,共M行。
约束:
1 ≤ N ≤ 100
0 ≤ M ≤ N×(N-1)/2
0 ≤ loads[i] ≤ 10000
0 ≤ edges[j][0], edges[j][1] ≤ N-1
edges[j][0] ≠ edges[j][1],无重复边
输出描述
整型,表示所有供电区中不均衡度的最大值。若无有效供电区,输出-1。
样例1
输入
[100,200,150,50,300],[[0,1],[1,2],[3,4]]
输出
500
说明
边(0,1)(1,2)将节点0,1,2连为供电区A,负载[100,200,150],不均衡度=(200-100)×3=300
边(3,4)将节点3,4连为供电区B,负载[50,300],不均衡度=(300-50)×2=500
供电区B不均衡度更大,输出500
样例2
输入
[80,90,80,90],[[0,1],[1,2],[2,3]]
输出
40
说明
4个节点连为1个供电区,不均衡度=(90-80)×4=40,输出40
样例3
输入
[100,200,300],[]
输出
-1
说明
每个节点独立,不构成有效供电区,输出-1