[文章目录]
Description
阿狸和桃子正在玩一个游戏，游戏是在一个带权图G=(V, E)上进行的，设节点权值为w(v)，边权为c(e)。游戏规则是这样的：
1. 阿狸和桃子轮流将图中的顶点染色，阿狸会将顶点染成红色，桃子会将顶点染成粉色。已经被染过色的点不能再染了，而且每一轮都必须给一个且仅一个顶点染色。
2. 为了保证公平性，节点的个数N为偶数。
3. 经过N/2轮游戏之后，两人都得到了一个顶点集合。对于顶点集合S，得分计算方式为
由于阿狸石头剪子布输给了桃子，所以桃子先染色。两人都想要使自己的分数比对方多，且多得越多越好。如果两人都是采用最优策略的，求最终桃子的分数减去阿狸的分数。
由于求最大分数相减，得分虑将边上的代价转移到点上。如果一条边两端点不属于同一个人，说明这条边对两点不做贡献。如果属于同一个点，那么贡献为c。
那就可以将边权均分到端点上。
如果c为奇数？？？直接代价都翻倍，然后ans除以2就好了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,w[11000];
long long ans;
bool cmp(int x,int y){return x>y;}
int main()
{
scanf("%d%d",&n,&m);
int x,y,z,i;
for(i=1;i<=n;++i) scanf("%d",w+i),w[i]<<=1;
while(m--)
{
scanf("%d%d%d",&x,&y,&z);
w[x]+=z; w[y]+=z;
}
sort(w+1,w+n+1,cmp);
for(i=1;i<=n;++i)
{
if(i&1) ans+=w[i];
else ans-=w[i];
}
printf("%lld",ans>>1);
return 0;
}