正題

題目鏈接:https://www.luogu.com.cn/problem/P4643

---

題目大意

給出$n$個(gè)點(diǎn)$m$條邊的無向圖，兩個(gè)人輪流選擇一個(gè)未被選擇的點(diǎn)加入點(diǎn)集。

然后每個(gè)人的權(quán)值為選出的點(diǎn)的導(dǎo)出子圖點(diǎn)權(quán)加邊權(quán)和。

兩個(gè)人都希望自己的權(quán)值減去對(duì)方的權(quán)值最大

求先手的權(quán)值減去后手的權(quán)值

$1\le n\le 10^4,1\le m\le 10^5$

---

解題思路

結(jié)論就是把邊權(quán)均分到點(diǎn)權(quán)處。

證明的話假設(shè)兩個(gè)點(diǎn)之間的點(diǎn)權(quán)為$w$。

那么如果兩邊顏色不同那么這個(gè)均分出來的權(quán)值會(huì)統(tǒng)計(jì)一個(gè)$\frac{w}{2}?\frac{w}{2}=0$的權(quán)值

如果兩邊顏色相同那么就會(huì)統(tǒng)計(jì)上這個(gè)權(quán)值。排序然后一個(gè)一個(gè)選就好了

時(shí)間復(fù)雜度$O(n\log n+m)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10; int n,m,w[N],v[N],p[N],x[N],y[N],e[N],ans; int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&w[i]),v[i]=w[i]*2,p[i]=i;for(int i=1;i<=m;i++){scanf("%d%d%d",&x[i],&y[i],&e[i]);v[x[i]]+=e[i];v[y[i]]+=e[i];}sort(v+1,v+1+n);for(int i=n;i>=1;i-=2)ans+=v[i]-v[i-1];printf("%d\n",ans/2);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P4643-[国家集训队]阿狸和桃子的游戏【结论】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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