将边权拆成两半加到它所关联的两个点的点权中即可
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;
}
补充：软件开发 , C++ ,
