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

题意：

阿狸和桃子正在玩一个游戏，游戏是在一个带权图 $G=(V, E)$ 上进行的，设节点权值为 $w(v)$ ，边权为 $c(e)$ 。游戏规则是这样的：

阿狸和桃子轮流将图中的顶点染色，阿狸会将顶点染成红色，桃子会将顶点染成粉色。已经被染过色的点不能再染了，而且每一轮都必须给一个且仅一个顶点染色。

为了保证公平性，节点的个数 $N$ 为偶数。

经过 $N/2$ 轮游戏之后，两人都得到了一个顶点集合。对于顶点集合 $S$ ，得分计算方式为

$\sum_{v \in S}w(v) + \sum_{e=(u,v)\in E \land u,v\in S}c(e)$
由于阿狸石头剪子布输给了桃子，所以桃子先染色。两人都想要使自己的分数比对方多，且多得越多越好。如果两人都是采用最优策略的，求最终桃子的分数减去阿狸的分数。

输入格式：

输入第一行包含两个正整数 $N$ 和 $M$ ，分别表示图 $G$ 的节点数和边数，保证 $N$ 一定是偶数。

接下来 $N+M$ 行。

前$N$ 行，每行一个整数 $w$ ，其中第 $k$ 行为节点 $k$ 的权值。

后 $M$ 行，每行三个用空格隔开的整数 $a ,b, c$ ，表示一条连接节点 $a$ 和节点 $b$ 的边，权值为 $c$ 。

输出格式：

输出仅包含一个整数，为桃子的得分减去阿狸的得分。

数据范围：

对于 $100\%$ 的数据，$1 \le N \le 10000, ~1 \le M \le 100000, ~-10000 \le w , c \le 10000$ 。

这个题的思路超级难想，一看题解恍然大悟。

边权不好处理，考虑化成点权

一个比较简单的想法是，直接把边权均分，两端点各拿一半

~~你敢信，这就是正解？~~ 然后我们来简单证明一下正确性

结论： $(u,v)$ 的边权均分至 $u,v$ ，贪心选择后最优。

简单证明：

如果一条边 $(u,v)$ 的端点都被 $A$ 选了

这样这条边的贡献算进去了，故结论成立。
如果一条边 $(u,v)$ 的端点 $u$ 被 $A$ 选了， $v$ 被 $B$ 选了

那么两边都得不到贡献，而因为
$a-b= x\Rightarrow (a+c)-(b+c)=x$
故结论仍成立。
不存在 $u,v$ 都没被选的情况。

时间复杂度 $O(n \log n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(1e4+15))

int n,m,res,a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i],a[i] <<= 1;
    for(int i=1,u,v,w; i<=m; i++)
        cin >> u >> v >> w, a[u] += w, a[v] += w;
    sort(a+1, a+1+n);
    for(int i=n; i; i-=2)
        res += a[i] - a[i-1];
    cout << (res >> 1) << '\n';
    return 0;
}