題目鏈接：點(diǎn)擊查看

題目大意：給出 $n$ 個(gè)點(diǎn)，每個(gè)點(diǎn)都有點(diǎn)權(quán)，再給出 $m$ 個(gè)關(guān)系，以 $(x,y,z)$ 的形式給出，規(guī)定如下：

同時(shí)選擇點(diǎn) $x$ 和點(diǎn) $y$ 將獲得 $z$ 的代價(jià)

選擇點(diǎn) $x$ 或點(diǎn) $y$ 將不獲得代價(jià)

同時(shí)不選擇點(diǎn) $x$ 和點(diǎn) $y$ 將獲得 $?z$ 的代價(jià)

問(wèn)如何選擇可以使得總代價(jià)最大

題目分析：假設(shè)把上述情況三去掉就是一個(gè)最大權(quán)閉合子圖的裸題了，導(dǎo)致想了半個(gè)小時(shí)的網(wǎng)絡(luò)流解法，雖然明知道是錯(cuò)誤的但卻并沒有什么新思路

賽后看了題解發(fā)現(xiàn)自己好像是之前在哪里見過(guò)這個(gè)模型，但是不記得了。。

正解就是初始時(shí)將答案 $ans$ 賦值為 $?z$ 之和，也就是初始時(shí)假設(shè)所有的點(diǎn)都不選，那么此時(shí)將點(diǎn) $x$ 和點(diǎn) $y$ 的點(diǎn)權(quán)都增加 $z$，此時(shí)就可以與題意契合：

同時(shí)選擇點(diǎn) $x$ 和點(diǎn) $y$ ，將獲得額外的 $?z+z+z=z$ 的代價(jià)

選擇點(diǎn) $x$ 或點(diǎn) $y$ ，將獲得 $?z+z=0$ 的代價(jià)

同時(shí)不選擇點(diǎn) $x$ 和點(diǎn) $y$ ，將獲得 $?z$ 的代價(jià)

最后貪心去取就好了

代碼：

class Solution { public:/*** 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可* * @param n int整型 * @param m int整型 * @param a int整型vector * @param b int整型vector<vector<>> * @return long長(zhǎng)整型*/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;} };

總結(jié)

以上是生活随笔為你收集整理的牛客 - 共鸣问题(贪心+思维)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。