BZOJ2563阿貍和桃子的游戲

2563: 阿貍和桃子的游戲

Time Limit:?3 Sec??Memory Limit:?128 MB
Submit:?952??Solved:?682
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

4 4
6
4
-1
-2
1 2 1
2 3 6
3 4 3
1 4 5

Sample Output

3
數(shù)據(jù)規(guī)模和約定
　　對于40%的數(shù)據(jù)，1 ≤ N ≤ 16。
　　對于100%的數(shù)據(jù)，1 ≤ N ≤ 10000，1 ≤ M ≤ 100000，-10000 ≤ w , c ≤ 10000。
題目大意：兩個人分別對一個圖的點染色。染到哪個點就會獲得哪個點的價值，如果一條邊的兩端被同一個人染色，那么 這個人也會獲得這條邊的價值。 題解：貪心 把一條邊的邊權(quán)分給兩端的點權(quán)，如果一條邊的兩端被兩人選擇，那么最后得分相減時會抵消 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 10006 6 using namespace std; 7 8 int n,m; 9 double sum1,sum2,w[maxn]; 10 11 int main() 12 { 13 scanf("%d%d",&n,&m); 14 for(int i=1;i<=n;i++)scanf("%lf",&w[i]); 15 for(int i=1;i<=m;i++) 16 { 17 int x,y,z; 18 scanf("%d%d%d",&x,&y,&z); 19 w[x]+=(double)(z/2.); 20 w[y]+=(double)(z/2.); 21 } 22 sort(w+1,w+n+1); 23 while(n) 24 { 25 sum1+=w[n--]; 26 sum2+=w[n--]; 27 } 28 printf("%.lf\n",sum1-sum2); 29 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/fengzhiyuan/p/8326169.html

總結(jié)

以上是生活随笔為你收集整理的bzoj 2563 贪心 思想的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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