题面：
阿狸和桃子正在玩一个游戏，游戏是在一个带权图\(\rm G=(V, E)\)上进行的，设节点权值为\(w(v)\)，边权为\(c(e)\)。游戏规则是这样的：
阿狸和桃子轮流将图中的顶点染色，阿狸会将顶点染成红色，桃子会将顶点染成粉色。已经被染过色的点不能再染了，而且每一轮都必须给一个且仅一个顶点染色。
为了保证公平性，节点的个数\(\rm N\)为偶数。
经过\(\rm N/2\)轮游戏之后，两人都得到了一个顶点集合。对于顶点集合S，得分计算方式为
\[\sum_{v \in S}w(v) + \sum_{e=(u,v)\in E \land u,v\in S}c(e)\]
由于阿狸石头剪子布输给了桃子，所以桃子先染色。两人都想要使自己的分数比对方多，且多得越多越好。如果两人都是采用最优策略的，求最终桃子的分数减去阿狸的分数。
\(\rm Sol\)
首先可以考虑没有边权的情况
那么就直接将点权排个序即可
如果有边权呢？
将每个边权拆成两半，一个给\(u\)一个给\(v\)
然后就会发现如果某两个点不在同一集合，那么这两点的权值差将会恰好抵消
\(Code:\)
#include<bits/stdc++.h>
using namespace std ;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
#define int long long
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ;
return cn * flus ;
}
const int N = 1e5 + 5 ;
int n, m ;
double A[N], Ans ;
signed main()
{
n = gi(), m = gi() ;
int x, y, z ;
rep( i, 1, n ) A[i] = gi() ;
rep( i, 1, m ) x = gi(), y = gi(), z = gi(), A[x] += 0.5 * z, A[y] += 0.5 * z ;
sort( A + 1, A + n + 1 ) ;
for( re int i = n; i >= 1; -- i ) {
Ans += ( ( i & 1 ) ? -1 : 1 ) * A[i] ;
}
printf("%lld\n", (int)Ans ) ;
return 0 ;
}