题目传送门(BZOJ)

题解 :

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

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>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原创, 转载必须以链接形式注明>原文链接<