洛谷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;
}