图中最大星和

There is an undirected graph consisting of n nodes numbered from 0 to n - 1. You are given a 0-indexed integer array vals of length n where vals[i] denotes the value of the ith node.

You are also given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.

A star graph is a subgraph of the given graph having a center node containing 0 or more neighbors. In other words, it is a subset of edges of the given graph such that there exists a common node for all edges.

The image below shows star graphs with 3 and 4 neighbors respectively, centered at the blue node.

The star sum is the sum of the values of all the nodes present in the star graph.

Given an integer k, return the maximum star sum of a star graph containing at most k edges.

 

Example 1:

Input: vals = [1,2,3,4,10,-10,-20], edges = [[0,1],[1,2],[1,3],[3,4],[3,5],[3,6]], k = 2
Output: 16
Explanation: The above diagram represents the input graph.
The star graph with the maximum star sum is denoted by blue. It is centered at 3 and includes its neighbors 1 and 4.
It can be shown it is not possible to get a star graph with a sum greater than 16.

Example 2:

Input: vals = [-5], edges = [], k = 0
Output: -5
Explanation: There is only one possible star graph, which is node 0 itself.
Hence, we return -5.

 

Constraints:

• n == vals.length
• 1 <= n <= 105
• -104 <= vals[i] <= 104
• 0 <= edges.length <= min(n * (n - 1) / 2, 105)
• edges[i].length == 2
• 0 <= ai, bi <= n - 1
• ai != bi
• 0 <= k <= n - 1

/*
 * 思路：
 * 1. 使用一个邻接表来表示图。
 * 2. 遍历每个节点，计算以该节点为中心节点的最大星和。
 * 3. 对于每个节点，首先获取它的所有邻居节点。
 * 4. 对这些邻居节点的值进行排序，选择值最大的k个邻居，计算它们的和。
 * 5. 将中心节点的值与选择的邻居节点的值之和计算出来即为星和。
 * 6. 返回所有星和中的最大值。
 */

import java.util.*;
import java.util.stream.Collectors;

public class MaxStarSumStream {
    public int maxStarSum(int[] vals, int[][] edges, int k) {
        int n = vals.length;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        return Arrays.stream(vals).map(i -> {
            List<Integer> neighbors = graph.get(i);
            return neighbors.stream()
                .map(neighbor -> vals[neighbor])
                .sorted(Collections.reverseOrder())
                .limit(k)
                .reduce(vals[i], Integer::sum);
        }).max(Integer::compareTo).orElse(Integer.MIN_VALUE);
    }
}

该题解主要采用了贪心策略和优先队列（最小堆）来解决问题。首先，为每个节点维护一个优先队列（最小堆），用来存储该节点的所有邻居节点的值，但只保留值最大的k个邻居。这是因为我们想要最大化星和，所以只保留最大的k个邻居值。当遍历每条边时，我们将节点值为正的邻居节点的值添加到对应的优先队列中。如果队列的长度超过k，则移除最小的元素，确保队列中只保留k个最大的值。在构建完所有节点的优先队列后，我们计算每个节点作为中心，其星和的最大值，即节点本身的值加上其优先队列中所有值的和，最后返回所有节点的最大星和。

O(m * log k + n * k)

O(n * k)