题意：给一个n个加权点m条加权边的无向图，两个人轮流拿走一个点，最后使先手得分-后手得分尽量大。一个人的得分等于拿到的点的点权和+边的两个端点在这个点集的边的边权和。（n<=10000, m<=100000）

#include 
     
      using namespace std;typedef long long ll;ll a[10005], ans;int main() {	int n, m;	scanf("%d%d", &n, &m);	for(int i=1; i<=n; ++i) {		scanf("%lld", &a[i]);		ans-=a[i];		a[i]<<=1;	}	for(int i=1; i<=m; ++i) {		int x, y, w;		scanf("%d%d%d", &x, &y, &w);		a[x]+=w; a[y]+=w; ans-=w;	}	sort(a+1, a+1+n);	for(int i=n; i>=1; i-=2)		ans+=a[i];	printf("%lld\n", ans);	return 0;}
     

　　

理解错题意了真蛋疼......

以为是求先手要最大化自己的得分，后手也要最大化自己的得分，求最终先手得分-后手得分......QAQ

其实是求，先手要最大化自己的得分-对方的得分.....................

于是就好做了（orz PoPoQQQ

考虑先手的选择对答案（先手得分-后手得分）的贡献：

1、选一个点$i$，$i$对答案贡献$w[i]$

2、不选点$i$，$i$对答案贡献$-w[i]$

3、选边$i$的一个端点，$i$对答案贡献$0$

4、选边$i$的两个端点，$i$对答案贡献$c[i]$

5、不选边$i$的两个端点，$i$对答案贡献$-c[i]$

考虑初始化答案为$-(\sum w[i] + \sum c[i])$

再来考虑上述情况的对答案的贡献：

1、贡献了$2w[i]$

2、贡献了$0$

3、贡献了$c[i]$

4、贡献了$2c[i]$

5、贡献了$0$

于是发现对点重赋值可以做到上面的情况！

即对点重赋值为：$2w[i]+\sum_{(i, j) \in E} c[(i, j)]$

然后每个人轮流取最大就是了= =