Description

　　阿貍和桃子正在玩一個游戲，游戲是在一個帶權圖G=(V, E)上進行的，設節點權值為w(v)，邊權為c(e)。游戲規則是這樣的：
　　1. 阿貍和桃子輪流將圖中的頂點染色，阿貍會將頂點染成紅色，桃子會將頂點染成粉色。已經被染過色的點不能再染了，而且每一輪都必須給一個且僅一個頂點染色。
　　2. 為了保證公平性，節點的個數N為偶數。
　　3. 經過N/2輪游戲之后，兩人都得到了一個頂點集合。對于頂點集合S，得分計算方式為
　　
　　。
　　由于阿貍石頭剪子布輸給了桃子，所以桃子先染色。兩人都想要使自己的分數比對方多，且多得越多越好。如果兩人都是采用最優策略的，求最終桃子的分數減去阿貍的分數。
　

Input

　輸入第一行包含兩個正整數N和M，分別表示圖G的節點數和邊數，保證N一定是偶數。
　　接下來N+M行。
　　前N行，每行一個整數w，其中第k行為節點k的權值。
　　后M行，每行三個用空格隔開的整數a b c，表示一條連接節點a和節點b的邊，權值為c。

Output

　輸出僅包含一個整數，為桃子的得分減去阿貍的得分。

Sample Input

4 464-1-21 2 12 3 63 4 31 4 5

Sample Output

3

數據規模和約定

　　對于40%的數據，1 ≤ N ≤ 16。

　　對于100%的數據，1 ≤ N ≤ 10000，1 ≤ M ≤ 100000，-10000 ≤ w , c ≤ 10000。

HINT

Source

2012國家集訓隊Round 1 day2

---

腦洞題…

讓求最優情況下，得分最小差值。

先不考慮點權。

因為讓求的是差值，取的是點，所以可以這樣思考：

邊權先設為w。
因為一條邊的兩個端點如果在同一個人手中，那他則會得到w分，對答案的貢獻為w分；若兩點在兩人手中，則對任意一人的貢獻皆為0分，對答案貢獻為0分。所以邊權為w的邊對它兩個端點的貢獻為：每個點w/2分。把這個貢獻加到點權里。

然后再加上它原來的點權，然后就可以看出最優策略：優先取點權大的點。

為了避免浮點數，可以乘2。

sort一遍完了。

Orz小綠

代碼：

#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std;int num[10000];int main() {int n,m;scanf("%d%d",&n,&m);for(int i = 1;i <= n;i ++){scanf("%d",&num[i]);num[i] *= 2;}for(int i = 1;i <= m;i ++){int a,b,c;scanf("%d%d%d",&a,&b,&c);num[a] += c;num[b] += c;}sort(num + 1,num + 1 + n);int ans1 = 0,ans2 = 0;for(int i = 1;i <= n;i ++){if(i & 1) ans2 += num[i];else ans1 += num[i];}printf("%d",(ans1 - ans2) / 2);return 0; }

總結

以上是生活随笔為你收集整理的【bzoj2563】阿狸和桃子的游戏 脑洞的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。