【洛谷4643】[国家集训队] 阿狸和桃子的游戏（水题）

点此看题面

大致题意： 有(n)个点（(n)为偶数），两个玩家轮流选择(frac n2)个点，最终得分为所有选中的点权加上两端都被选中的边权。求最优策略下先手得分与后手得分之差。

边权分配

考虑我们把一条边((x,y,w))的边权(w)分配给点，即将(x,y)的点权分别加上(frac w2)。

如果(x,y)被一个人选中，得到(w)的贡献。

如果(x,y)被不同人选中，分配的权值会抵消不产生影响。

而只剩点权之后只要每次贪心选择点权最大的点即可。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 10000
using namespace std;
int n,m,a[N+5];priority_queue<int> q;
int main()
{
	RI i,x,y,z,ans=0;for(scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",a+i),a[i]<<=1;//将a[i]乘2避免出现小数
	for(i=1;i<=m;++i) scanf("%d%d%d",&x,&y,&z),a[x]+=z,a[y]+=z;//边权分配
	for(i=1;i<=n;++i) q.push(a[i]);for(i=1;i<=n/2;++i) ans+=q.top(),q.pop(),ans-=q.top(),q.pop();//贪心
	return printf("%d
",ans>>1),0;//输出答案，记得除以2
}