# 2497. Maximum Star Sum of a Graph
###### tags: `Leetcode` `Medium` `Greedy` `Sorting` `Priority Queue`
Link: https://leetcode.com/problems/maximum-star-sum-of-a-graph/description/
## 思路
尝试以每个点为中心点 并找到最多k个edge的maximum sum
在里面取最大的即可
对于任意点A来说 maximum sum就是它的val+前k大的neighbor weight(不包含任何小于0的数)
所以可以用sorting或者[priority queue实现](https://leetcode.com/problems/maximum-star-sum-of-a-graph/solutions/2897910/very-easy-cpp-solution-with-explanation-priority-queue/?orderBy=most_votes)
## Code

class Solution {
    public int maxStarSum(int[] vals, int[][] edges, int k) {
        int n = vals.length;
        List<List<Integer>> weightList = new ArrayList<>();
        for(int i=0; i<n; i++){
            weightList.add(new ArrayList<>());
        }
        for(int[] edge:edges){
            weightList.get(edge[0]).add(vals[edge[1]]);
            weightList.get(edge[1]).add(vals[edge[0]]);
        }
        for(int i=0; i<n; i++) Collections.sort(weightList.get(i), Collections.reverseOrder());
        int maxSum = Integer.MIN_VALUE;
        for(int i=0; i<n; i++){
            int curSum = vals[i];
            for(int j=0; j<Math.min(k, weightList.get(i).size()); j++){
                if(weightList.get(i).get(j)<0) break;
                curSum += weightList.get(i).get(j);
            }
            maxSum = Math.max(maxSum, curSum);
        }
        return maxSum;
    }
}