每日一题：共鸣问题

题意

现在有 $n$ 个音符和 $m$ 对共鸣关系，编号为 $1-n$，每个音符自己有一个奏响时的优美程度，共鸣关系 $(x,y,z)$ 表示音符 $x$ 和 $y$ 同时奏响的额外优美程度是 $z$，同时不奏响则为 $-z$，其他情况为 $0$，求最大优美程度。$(n,m \in [1,1e5])$

思路

对于一对共鸣关系而言，在不选的情况下收益为 $-z$，则选择一个的话，收益为 $-z + z = 0$，都选择的话为 $-z + 2z = z$。因此可以预先把每对关系的两个数都加上 $z$，刚开始我们是不选任何有联系的音符的，因此初值为 $-z$，那么选择一个数就会加上 $z$，选择两个就会加上 $2z$，满足了之前所讨论的关系。答案初始化为所有关系都不选的情况，即 $-sum(z)$，然后只要贪心的选择对答案有正贡献的值就行了。

Code

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @param m int整型 
     * @param a int整型vector 
     * @param b int整型vector<vector<>> 
     * @return long长整型
     */
    long long wwork(int n, int m, vector<int>& a, vector<vector<int> >& b) {
        // write code here
        vector<long long> c;
        long long res = 0;
        for (auto& x : a) c.push_back(x);
        for (auto& v : b) {
            c[v[0] - 1] += v[2];
            c[v[1] - 1] += v[2];
            res -= v[2];
        }
        for (auto& x : c) res += max(x, 0);
        return res;
    }
};