题解 P4643 【[国家集训队]阿狸和桃子的游戏】
rui_er
2020-08-11 16:26:45
**题意简述**
我们有一个 $n$ 点 $m$ 边的无向图，有点权和边权。现在两个人将它按照自己的最优方案每次取一个点，分为两部分，求出此时他们的分差。
---
**方法分析**
边权不好处理，我们想到将它与点权合并。最容易想到的方法就是两个端点各加一半边权，这个方法也是正确的，正确性将在下方证明。
因为每个人都会按照自己的当前最优策略取，所以将整个权值排序后，编号为奇数的是一个人取的，偶数的是另一个人取的，我们只需要按照奇偶数分别算出总权值即可。
**正确性证明**
这里主要证明上面说的将边权与点权合并的正确性。
对于一条边 $e(u,v,w)$，设两端点的初始权值为 $a_u,a_v$，我们这里将两端点的权值改为了 $a_u+\frac{w}{2},a_v+\frac{w}{2}$。
情况一：$u,v$ 被同一个人取到。
此时，这个人的总权值为 $a_u+a_v+2\times\frac{w}{2}=a_u+a_v+w$，符合题意。
情况二：$u,v$ 被两人分别取到。
不妨设 $u$ 被第一个人取到。
此时，第一个人权值为 $a_u+\frac{w}{2}$，第二个人权值为 $a_v+\frac{w}{2}$。最后要将答案相减，得到 $a_u-a_v$，符合题意。
综上所述，这种方法正确。
---
**代码与备注**
在这份代码中，我们排序后按照从小到大顺序循环取值。由于题面保证 $n$ 为偶数，因此这个方法也没有问题。
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
int n, m;
double a[N], s[2];
int main() {
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++) scanf("%lf", &a[i]);
for(int i=1;i<=m;i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
a[u] += w / 2.0;
a[v] += w / 2.0;
}
sort(a+1, a+1+n);
for(int i=1;i<=n;i++) s[i&1] += a[i];
printf("%.0lf\n", s[0]-s[1]);
return 0;
}
```