题目大意：给定一张无向图，每个点有点权，每条边有边权，两个人轮流选择点，若一条边的两端点被选择则这条边被选择，两人都想自己的得分-对手的得分最大，求最终先手得分-后手得分
考虑先手选择每个点对答案的影响
一个点如果不选，本身对答案的贡献是-w
一个点如果选，本身对答案的贡献是w
一条边如果两个端点都不选，对答案的贡献是-c
如果两个端点中只选择一个，对答案的贡献是0
如果两个端点都选，对答案的贡献是c
那么我们先预先把所有的权值都在初始答案中减掉，然后就变成了：
一个点如果不选，本身对答案的贡献是0
一个点如果选，本身对答案的贡献是2*w
一条边如果两个端点都不选，对答案的贡献是0
如果两个端点中只选择一个，，对答案的贡献是c
如果两个端点都选，对答案的贡献是2*c
那么令一个点的贡献值为本身点权的二倍+所有相连的边的边权
排个序两人轮流取最大即可
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 10100using namespace std;int n,m;long long ans,a[M];int main(){int i,x,y,z;cin>>n>>m;for(i=1;i<=n;i++){scanf("%d",&z);ans-=z;a[i]=z<<1;}for(i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);ans-=z;a[x]+=z;a[y]+=z;}sort(a+1,a+n+1);for(i=2;i<=n;i+=2)ans+=a[i];cout<<ans<<endl;return 0;}
总在盼望未来,愿你的人生美开
