將邊權拆成兩半加到它所關聯的兩個點的點權中即可

1005:

若沒有邊權，則對點權從大到小排序即可。。

考慮邊，將邊權拆成兩半加到它所關聯的兩個點的點權中即可。

。。因為當兩個人分別選擇不同的點時，這一權值將互相抵消。

智商是硬傷啊

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
using namespace std;
double w[100001];
int main()
{
    //freopen("1005.in","r",stdin);
    int n,m,i,a,c,b;
    while(~scanf("%d%d",&n,&m))
    {
        memset(w,0,sizeof(w));
        for(i=1;i<=n;i++)scanf("%lf",&w[i]);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            w[a]+=1.0*c/2;
            w[b]+=1.0*c/2;
        }
        double s;
        s=0;
        sort(w+1,w+n+1);
        for(i=n;i>=1;i-=2)
        {
            s+=w[i]-w[i-1];
        }
        printf("%.0lf\n",s);
    }
    return 0;
}