题意：

一个n（偶数）点图，节点权值为w(v)，边权为c(e)。两人轮流将图中的顶点染色，已经被染过色的点不能再染了，而且每一轮都必须给一个且仅一个顶点染色。染完后每个人的分数为染过的点权和以及两个端点都被染的边权和。如果两人都是采用最优策略的，求最终第一个人的分数减去第二个人的分数。n≤10000，边数≤100000

题解：

本弱只能引用神犇的题解

“

考虑先手选择每个点对答案的影响

一个点如果不选，本身对答案的贡献是-w，一个点如果选，本身对答案的贡献是w，一条边如果两个端点都不选，对答案的贡献是-c，如果两个端点中只选择一个，对答案的贡献是0，如果两个端点都选，对答案的贡献是c，那么我们先预先把所有的权值都在初始答案中减掉，然后就变成了：

一个点如果不选，本身对答案的贡献是0，一个点如果选，本身对答案的贡献是2*w，一条边如果两个端点都不选，对答案的贡献是0，如果两个端点中只选择一个，对答案的贡献是c，如果两个端点都选，对答案的贡献是2*c，那么令一个点的贡献值为本身点权的二倍+所有相连的边的边权，排个序两人轮流取最大即可。

”

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define maxn 10010 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define ll long long 7 using namespace std; 8  9 int n,m; ll w[maxn],ans1,ans2;10 bool cmp(ll a,ll b){
   return a>b;}11 inline int read(){12     char ch=getchar(); int f=1,x=0;13     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();14     return f*x;15 }16 int main(){17     n=read(); m=read(); inc(i,1,n)w[i]=(ll)read()<<1,ans2+=w[i]>>1;18     inc(i,1,m){
   int a=read(),b=read(); ll c=(ll)read(); ans2+=c; w[a]+=c; w[b]+=c;} sort(w+1,w+n+1,cmp);19     inc(i,1,n){
   if(i&1)ans1+=w[i];}20     printf("%lld",ans1-ans2); return 0;21 }
       
      
     

 

20160623