Miku

贪心，只有点权的时候显然好做，但是还有边权怎么办呢

假设这里有一条边，边权为2v，然后两个点的点权为a，b,我们把边权分成两部分，然后平摊到两个点上，那么

边权变成了a+V,B+V

假如一人选了一个选了 那么a+V-(b+v) 和a-b一样。

同理，假如两个都归了一个人，那么a+V+b+v和-a-b-v-v显然和原来等效

由此可知，这么做是正确的

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int f[100001];
int x,y,z;
long long a,b;
bool cmp(int x,int y){
    return x>y;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&f[i]);
        f[i]*=2;
    }
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&x,&y,&z);
        f[x]+=z;
        f[y]+=z; 
    }
    sort(f+1,f+n+1,cmp);
    for(int i=1;i<=n;++i){
        if(i%2)
        a+=f[i];
        else
        b+=f[i];
    }
    cout<<(a-b)/2;
    return 0;

}