hdu 4647 Another Graph Game

点击打开hdu 4647

思路: 贪心

1 若没有边权，则对点权从大到小排序即可

2 考虑边，将边权拆成两半加到它所关联的两个点的点权中即可。因为当两个人分别选择不同的点时，这一权值将互相抵消
3 如果把边折半的时候可能是把边权为奇数，那么我们在处理的时候就把所有的权值乘以2，然后最后ans/2即可

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long int64;
const int MAXN = 100010;

int n , m;
int64 val[MAXN];

int main(){
    int x , y , v;
    while(scanf("%d%d" , &n , &m) != EOF){
         for(int i = 1 ; i <= n ; i++){
             scanf("%d" , &v);
             val[i] = 2*v;
         }
         for(int i = 0 ; i < m ; i++){
             scanf("%d%d%d" , &x, &y , &v); 
             val[x] += v;
             val[y] += v;
         }
         sort(val+1 , val+n+1);
         int64 sum1 , sum2;
         sum1 = sum2 = 0;
         for(int i = 1 ; i <= n ; i += 2){
             sum1 += val[i]; 
             if(i <= n)
                sum2 += val[i+1]; 
         }
         printf("%lld\n" , abs(sum1-sum2)/2);
    } 
    return 0;
}