[国家集训队]阿狸和桃子的游戏——贪心+博弈论

AubRain · 2018-11-29 15:35:03 · 题解

简单的博弈。

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

为什么是对的？

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

代码 13 行，短得可怜

#include<bits/stdc++.h>
using namespace std;
int n,m,a[10005],ans;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]<<=1;
    for(int x,y,v,i=1;i<=m;i++)
        cin>>x>>y>>v,a[x]+=v,a[y]+=v;
    sort(a+1,a+1+n);
    while(n) ans+=a[n--]-a[n--];
    cout<<ans/2;
}