牛客 - 共鳴問題(貪心+思維)

題目鏈接：點擊查看

題目大意：給出 n n n 個點，每個點都有點權，再給出 m m m 個關系，以 ( x , y , z ) (x,y,z) (x,y,z) 的形式給出，規定如下：

1. 同時選擇點 x x x 和點 y y y 將獲得 z z z 的代價
2. 選擇點 x x x 或點 y y y 將不獲得代價
3. 同時不選擇點 x x x 和點 y y y 將獲得 ? z -z ?z 的代價

問如何選擇可以使得總代價最大

題目分析：假設把上述情況三去掉就是一個最大權閉合子圖的裸題了，導致想了半個小時的網路流解法，雖然明知道是錯誤的但卻并沒有什么新思路

賽后看了題解發現自己好像是之前在哪里見過這個模型，但是不記得了，，

正解就是初始時將答案 a n s ans ans 賦值為 ? z -z ?z 之和，也就是初始時假設所有的點都不選，那么此時將 x x x 和點 y y y 的點權都增加 z z z，此時就可以與題意契合：

1. 同時選擇點 x x x 和點 y y y ，將獲得額外的 ? z + z + z = z -z + z + z=z ?z+z+z=z 的代價
2. 選擇點 x x x 或點 y y y ，將獲得 ? z + z = 0 -z + z = 0 ?z+z=0 的代價
3. 同時不選擇點 x x x 和點 y y y ，將獲得 ? z -z ?z 的代價

最后貪心去取就好了

代碼：

class Solution {
public:
    /**
     * 代碼中的類名、方法名、引數名已經指定，請勿修改，直接回傳方法規定的值即可
     * 
     * @param n int整型 
     * @param m int整型 
     * @param a int整型vector 
     * @param b int整型vector<vector<>> 
     * @return long長整型
     */
    long long c[100100];
    long long wwork(int n, int m, vector<int>& a, vector<vector<int> >& b) {
        long long ans=0;
        for(int i=0;i<n;i++) c[i+1]=a[i];
        for(auto it:b) c[it[0]]+=it[2],c[it[1]]+=it[2],ans-=it[2];
        for(int i=1;i<=n;i++) ans+=max(0LL,c[i]);
        return ans;
    }
};