如果你相信洛谷的难度评级，你还不如去买彩票。
——zhx长者

题意描述：

阿狸和桃子正在玩一个游戏，游戏是在一个带权图 $G=(V, E)$ 上进行的，设节点权值为$w(v)$，边权为$c(e)$。

游戏规则如下：

1.阿狸和桃子轮流将图中的顶点染色，阿狸会将顶点染成红色，桃子会将顶点染成粉色。已经被染过色的点不能再染了，而且每一轮都必须给一个且仅一个顶点染色。

2.为了保证公平性，节点的个数N为偶数。

3.经过 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。

输出格式：

　输出仅包含一个整数ans，为桃子的得分减去阿狸的得分。

Input & Output ‘s examples

Input ‘s eg

4 4
6
4
-1
-2
1 2 1
2 3 6
3 4 3
1 4 5

Output ‘s eg

3

数据范围和约定：

对于40%的数据，1 ≤ N ≤ 16。
对于100%的数据，1 ≤ N ≤ 10000，1 ≤ M ≤ 100000，-10000 ≤ w , c ≤ 10000。

分析

蓝题的思维难度 + 橙题的代码量 = 一道黑题
——Herself32

简单的博弈论问题（逃）

而且一定有人看不懂公式（逃 X2）

那……

我们就先来解释一下公式吧。

下面是公式翻译机：

经过 N/2 轮游戏之后，两人都会得到一个顶点集合。对于顶点集合S，得分计算方式为:

他们染色的顶点点权 + 他们同种颜色的顶点组成线段的边权

还不会做？

好吧……

画个图解释下~~(你们绝对看不出我是用画图手绘的)~~

这是两个点，点权为A & B，中间的边权为C，答案记为ans

如果两个点都被桃子染了，就像这样

那么，ans = 桃子的得分 - 阿狸的得分 = A + B + C

但，如果我们吧边权二分，分给每个节点

ans = (A + C / 2) + (B + C / 2) = A + B + C

答案是不变的

同理，阿狸也是这样。但如果他们一人染了一个点，就像下图这样

边权二分还可以吗？

答案是肯定的。

在不二分的情况下，中间边权可以忽略，则ans = B - A

如果二分，则答案为ans = (B + C / 2) - (A + C / 2) = B - A

综上所述，二分边权是可行的。

是不是很简单(逃 X3)

附件（AC标程，防作弊已开启）

#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
int point[100001],w[100001];
int a,b,c;
int ans;
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i ++){
		cin >> w[i];
		point[i] = 2 * w[i];
	}
	for(int i = 1; i <= m; i ++){
		cin >> a >> b >> c;
		point[a] = point[a] + c;
		point[b] = point[b] + c;
	}
	int x = 1;
	sort(point + 1, point + 1 + n);
	while(n >= 0){
		ans = point[n--] - point[n--] + ans;
	}
	cout << ans / 2;
	return 0;
}