Luogu

BZOJ

分析

发现这个边权不太好搞，于是考虑化成点权。

如果有一条边$(u,v,w)$，那么将$u$的点权增加$w/2$，将$v$的点权增加$w/2$。

正确性？分情况讨论：

• 如果$\text{A}$同时染了$u$和$v$，那么它还是可以得到$w$。
• 如果$\text{A}$染了$u$，$\text{B}$染了$v$，那么它们都多得了$w/2$，差不变。

这样之后，显然可以贪心地选，每次染点权大的点。

然后，为了避免浮点数，可以将所有数据乘$2$再运算，最后结果除以$2$。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000+10;

int n,m,ans;
int val[N];
inline int cmp(int x,int y) { return x>y; }

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) val[i]=read()<<1;
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read(),w=read();
        val[u]+=w,val[v]+=w;
    }
    sort(val+1,val+n+1,cmp);
    for (re int i=1;i<=n;i+=2) ans+=val[i]-val[i+1];
    printf("%d\n",ans>>1);
    return 0;
}