【LG P4643】阿狸和桃子的游戏

题意简述

我们有一个 (n) 点 (m) 边的无向图，有点权和边权。现在两个人将它按照自己的最优方案每次取一个点，分为两部分，求出此时他们的分差。

思路

把边权转换为点权即可。具体来说，把一条边的边权各一半加到两个顶点上，然后每个人选的时候，贪心的选取点权最大的点即可。

简要证明：如果一条边的两个顶点被同一个人选上了，那么它就会额外提供等同于边权的贡献；否则的话，两个人每人都有一半边权的收益，相当于这条边谁也没给，也是符合题意的。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int a[N];
int main() {
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1; i<=n; i++) {
		scanf("%d",a+i),a[i]<<=1;
	}
	for(int i=1,x,y,z; i<=m; i++) {
		scanf("%d %d %d",&x,&y,&z),a[x]+=z,a[y]+=z;
	}
	sort(a+1,a+n+1);
	int ans=0;
	for(int i=n; i; i-=2) {
		ans+=a[i]-a[i-1];
	}
	printf("%d",ans>>1);
	return 0;
}