洛谷P4643 [国家集训队]阿狸和桃子的游戏（思维题+贪心）

佚名 6年前 (2019-04-16) 随笔 1779人围观抢沙发百度已收录

思维题，好题

把每条边的边权平分到这条边的两个顶点上，之后就是个sb贪心了

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

正确性证明：

如果一条边的两个顶点被一个人选了，一整条边的贡献就凑齐了

如果分别被两个人选了，一作差就抵消了，相当于谁都没有

代码

#include <bits/stdc++.h>
#define rep(i,x,y) for(i=(x);i<=(y);++i)
using namespace std;
double a[10010];
int main(){
    int n,m,i,x,y,z;
    double ans[2];
    scanf("%d%d",&n,&m);
    rep(i,1,n) scanf("%lf",&a[i]);
    rep(i,1,m){
        scanf("%d%d%d",&x,&y,&z);
        a[x]+=1.0*z/2.0,a[y]+=1.0*z/2.0;
    }
    sort(a+1,a+n+1);
    for(i=n;i>=1;--i) ans[i&1]+=a[i];
    printf("%.0f",ans[n&1]-ans[(n&1)^1]);
}