BZOJ 2563: 阿狸和桃子的游戏 – [贪心]

题目传送门(BZOJ)

题解 :

我们把边权平分给两个端点
若一个人拿到了这两个点, 那么这条边权已经给他了
若两个人分别拿到了这两个点, 那么两个一半边权会抵消
由于都是最优策略, 那么把所有点权排个序, 两个人轮流取当前最大即可
比较关键的还是能想到把边权拆开
为了防止精度问题, 我们把所有权值都乘 2 , 最后答案除以 2 就行了

代码 :

#include 
#include 
#include 
#include 
using namespace std;
const int N = 11000;
int a[N], n, m, opt = 1, ans = 0;
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]), a[i] <<= 1;
    for(int i = 1; i <= m; i ++ ) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        a[u] += w;
        a[v] += w;
    }
    sort(a+1, a+n+1); reverse(a+1, a+n+1);
    for(int i = 1; i <= n; i ++ ) {
        ans += opt*a[i];
        opt = -opt;
    }
    printf("%d\n", ans >> 1);
}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<