Show problems as
Classic problem #2497MediumArrayGreedyGraph TheorySortingHeap (Priority Queue)

Maximum Star Sum of a Graph

Real-world version: Best Hub and Spokes Yield
Tracked in this browser only
Read Maximum Star Sum of a Graph on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A survey network has n sites numbered 0 through n - 1. Site i reports a yield of vals[i], which may be negative. edges[j] = [a, b] is a two-way cable between site a and site b.

A cluster is one site chosen as the hub, together with any set of at most k sites that share a cable with it. The hub is always part of its own cluster, and a cluster may consist of the hub alone. The yield of a cluster is the sum of the yields of its sites.

Return the largest yield any cluster can have.

Examples

Example 1

Input
vals = [2, -1, 5, -3], edges = [[0, 1], [0, 2], [1, 3]], k = 2
Output
7

Taking site 0 as the hub and site 2 as its only spoke gives 2 + 5 = 7. Sites 0 and 2 do share a cable, and one spoke is within the allowance of two.

Example 2

Input
vals = [-5, -6, -7], edges = [[0, 1], [1, 2]], k = 2
Output
-5

Every yield is negative. A cluster of site 0 alone has yield -5, and no cluster does better.

Example 3

Input
vals = [10, 0, 0], edges = [[0, 1], [0, 2]], k = 2
Output
10

Site 0 as the hub gives 10, and adding either zero-yield spoke leaves the total at 10, so 10 is the largest yield.

Constraints

  • 1 <= vals.length <= 10^5
  • -10^4 <= vals[i] <= 10^4
  • 0 <= edges.length <= 10^5
  • edges[j].length == 2
  • 0 <= edges[j][0] <= 99999
  • 0 <= edges[j][1] <= 99999
  • A cable never joins a site to itself, and every site index is below vals.length
  • 0 <= k <= 99999

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def best_hub_yield(vals: list[int], edges: list[list[int]], k: int) -> int:
Java
public int bestHubYield(int[] vals, int[][] edges, int k)

More on the same topics