题解 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;
}
```