智商好题
对于一条边的两个端点x、y，我们把边权的一半附给他们
这样如果两点都选则贡献为v[x]+v[y]+e[i].v
如选其中一点，贡献为v[x]+e[i].v/2-v[y]-e[i].v/2=v[x]-v[y]
和原问题等价
将新的点权排序即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| #include<bits/stdc++.h> #define FILE "read" using namespace std; int n,m; double ans[2],v[10010]; inline int read(){ int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x*f; } bool cmp(double a,double b){return a>b;} int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); n=read(); m=read(); for(int i=1;i<=n;++i) v[i]=(double)read(); for(int i=1;i<=m;++i){ int x=read(),y=read(),val=read(); v[x]+=(double)val/2; v[y]+=(double)val/2; } sort(v+1,v+n+1,cmp); for(int i=1;i<=n;++i) ans[i&1]+=v[i]; printf("%d\n",(int)(ans[1]-ans[0])); return 0; }
|