题解 P4643 【[国家集训队]阿狸和桃子的游戏】

题目链接

Solution [国家集训队]阿狸和桃子的游戏

题目大意：给定一张图，点(个数为偶数)和边都有权值，两个人轮流染色，对点染色可以直接得到点的权值，若一边两点被同一个人染色还可以得到边的权值。两个人都按照最优策略染色，求最后两个人分数差的绝对值

贪心

---

分析：此题关键在于转化，既然我们只关心两个人的分数差，我们可以将边权平分给两个点，然后直接对点权贪心即可

证明如下：

1.两个点被同一个人染色，那个人得到两个点权，相当于原来边权

2.两个点被两个人染色，每人得到同样的点权，相当于没人得到边权

转化过后按照点权从大到小的顺序贪心即可，方便起见，可以将所有权值乘(2)，最后除(2)即可

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 100;
int v[maxn],n,m;
ll ans;
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= n;i++)scanf("%d",v + i),v[i] *= 2;
    for(int a,b,c,i = 1;i <= m;i++){
        scanf("%d %d %d",&a,&b,&c);
        v[a] += c,v[b] += c;
    }
    sort(v + 1,v + 1 + n,[](int a,int b){return a > b;});
    for(int i = 1;i <= n;i += 2)ans += v[i];
    for(int i = 2;i <= n;i += 2)ans -= v[i];
    printf("%lld
",ans >> 1);
    return 0; 
}