20260614-分析电网负载均衡（N003）- 算法机考高频题型 · 华为OD / DFS题解 | AlgoMooc

N0038. 20260614-分析电网负载均衡

中等

通过率 87% · 提交 15 · 通过 13

华为ODDFSBFS

本题改编自算法机考高频题型 · 考点：华为OD / DFS · 难度：中等

某电力公司管理 N 个变电站节点（编号 0∼N−1），节点间通过 M 条输电线路连接，相连节点属于同一供电区。定义供电区的不均衡度 = 区内最大负载与最小负载之差 × 节点数。请找出不均衡度最大的供电区，输出其不均衡度。若无有效供电区（节点数 < 2 或 M=0 ），输出 -1。

这类题属于算法机考高频题型中「华为OD / DFS」方向的高频题型，通常考察对「华为OD / DFS」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。

输入描述

输入两个参数：

整型数组 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

输入示例

5
100,200,150,50,300
3
0,1
1,2
3,4

输出示例

说明：

边(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

输入示例

4
80,90,80,90
3
0,1
1,2
2,3

输出示例

说明：

4个节点连为 1 个供电区，不均衡度= (90 - 80)× 4 = 40 ，输出 40

示例 3

输入示例

3
100,200,300
0

输出示例

-1

说明：

每个节点独立，不构成有效供电区，输出-1

时间限制 1000 ms · 内存限制 256 MB

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

问小欧 · 图解算法年卡¥99 开通 →

字号13Ctrl+/ 注释 · Ctrl+↵ 提交

from typing import List
from collections import deque, defaultdict

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# @param loads: 整型数组，长度为N，表示编号0~N-1的节点负载(MW)
# @param edges: 二维整型数组，每行2个整数，表示该线路连接的两个节点编号
# @return: 整型，表示所有供电区中不均衡度的最大值，若无有效供电区输出-1
class Solution:
    def maxUnbalance(self, loads: List[int], edges: List[List[int]]) -> int:


# 以下内容为LeetCode核心代码模式转为ACM模式所需代码
# 请在algomooc oj上直接使用，在实际考试中无需编写

def main():
    import sys
    input = sys.stdin.readline

    n = int(input().strip())
    loads = list(map(int, input().strip().split(',')))
    m = int(input().strip())
    edges = []
    for _ in range(m):
        line = input().strip()
        if not line:
            continue
        u, v = map(int, line.split(','))
        edges.append([u, v])

    sol = Solution()
    print(sol.maxUnbalance(loads, edges))


if __name__ == "__main__":
    main()

写完代码点「提交」，将对全部测试用例判题。