阿狸和桃子的游戏：Lucyna 推荐的简单诈骗题。
直接对每次两人操作对答案的增量考虑，发现如果一条边被同一个人选择，那么贡献就是 \(w\)；否则贡献就是 \(0\)。而如果把这个贡献均摊到每次给点染色的操作中，贡献就可以定为 \(\dfrac{w}{2}\)。容易发现答案就是桃子选的贡献减去阿狸选的贡献。于是把边权转点权，然后排序一下，贪心选即可。
时间复杂度 \(O(n\log n)\)，用桶排序可以做到 \(O(n)\)。注意除以 \(2\) 的处理方式，可以将点权先全部乘 \(2\)，最后输出答案的时候再把答案除以 \(2\) 即可。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi=pair<int,int>;
const int N = 10005;
int n, m;
ll a[N], ans;
int main()
{//freopen("sample.in","r",stdin);//freopen("sample.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; i++){cin >> a[i];a[i] = a[i] * 2;}for(int i = 1; i <= m; i++){int u, v, w;cin >> u >> v >> w;a[u] += w;a[v] += w;}sort(a + 1, a + n + 1);for(int i = n; i >= 1; i -= 2) ans += a[i] - a[i - 1];cout << ans / 2;return 0;
}