最小生成树的变形——将边权赋予到点权（当然还有一种是将点权赋到边权）

显然将边权分一半给旁边的点，然后最小生成树就可以了。

因为如果两个人分别把这个边两边的点选走了，他们相当于谁都没有拿到这个边的边权。但是如果一个人拿到了两个点，就相当于拿到了这条边的边权。

直接贪心即可》》》

不过需要注意的是将边权除以二的时候可能会出现小数，所以我们预先把它乘上二，最后输出答案的时候再除掉就可以了。

代码如下：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define MAXN 100010using namespace std;int n,m;int v[MAXN];long long ans;int main(){    #ifndef ONLINE_JUDGE    freopen("ce.in","r",stdin);    #endif    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++) scanf("%d",&v[i]),v[i]<<=1;    for(int i=1;i<=m;i++)    {        int a,b,c;        scanf("%d%d%d",&a,&b,&c);        v[a]+=c,v[b]+=c;    }    sort(&v[1],&v[n+1]);    for(int i=1;i<=n;i+=2)        ans+=v[n-i+1]-v[n-i];    printf("%lld\n",ans/2);}