zhx神仙说过一句话：如果你相信Luogu的难度评级，那你还不如买彩票。

题目描述

阿狸和桃子正在玩一个游戏，游戏是在一个带权图G=(V, E)上进行的，设节点权值为w(v)，边权为c(e)。游戏规则是这样的：

阿狸和桃子轮流将图中的顶点染色，阿狸会将顶点染成红色，桃子会将顶点染成粉色。已经被染过色的点不能再染了，而且每一轮都必须给一个且仅一个顶点染色。
为了保证公平性，节点的个数N为偶数。
经过N/2轮游戏之后，两人都得到了一个顶点集合。对于顶点集合S，得分计算方式为

$$\sum_{v \in S}w(v) + \sum_{e=(u,v)\in E \land u,v\in S}c(e)$$

由于阿狸石头剪子布输给了桃子，所以桃子先染色。两人都想要使自己的分数比对方多，且多得越多越好。如果两人都是采用最优策略的，求最终桃子的分数减去阿狸的分数。

输入输出格式

输入格式

输入第一行包含两个正整数N和M，分别表示图G的节点数和边数，保证N一定是偶数。

接下来N+M行。

前N行，每行一个整数w，其中第k行为节点k的权值。

后M行，每行三个用空格隔开的整数a b c，表示一条连接节点a和节点b的边，权值为c。

输出格式

输出仅包含一个整数，为桃子的得分减去阿狸的得分。

INPUT & OUTPUT’s examples

Input’s e.g. #1

Output’s e.g. #1

说明

数据规模和约定对于40%的数据，1 ≤ N ≤ 16。对于100%的数据，1 ≤ N ≤ 10000，1 ≤ M ≤ 100000，-10000 ≤ w , c ≤ 10000。

分析

蓝题的思考难度，橙题的实现难度，成就了这样一道黑题。

其实Luogu上一位神仙已经讲得非常清楚了，但由于TA画的图不太美观（雾，十分不利于理解，窝就再来讲一遍。

假设我们有这样一条边，其连接两个点权分别为$a,b$,而这条边的边权为$c$。

然后我们可以考虑把边权转化到点权上，这样就会好处理很多。

我们首先猜想：把边权二分，每一半分别给两个点。

怎么证明正确性呢？

我们知道，有三种情况，那么我们一一证明。

1. 当两人中的任何一方占领了一条边连接的两个节点：

那么这个人的得分就是$a+b+c$,另一个人得分为$0$.

所以两人的分差为 $a+b+c-0 = a+b+c$.

二分之后，这个人的得分为$(a + \frac{c}{2}) + (b + \frac{c}{2}) = a+b+c$,另一个人得分也是$0$.

所以两人的分差为 $a+b+c-0 = a+b+c$.

2. 当两人分别占领了一条边连接的两个节点时：

那么两人得分为$a $ 和 $b$.

所以两人分差为$a-b = a-b$。

二分之后，两人得分分别为$a + \frac{c}{2}$ 和 $b + \frac{c}{2}$.

所以两人分差为$(a + \frac{c}{2}) - (b + \frac{c}{2}) = a-b$

证毕。

其实这题代码实现根本和图论一点关系都没有QAQ。

最后再提一下：为了防止二分的时候出现精度误差，我们把$a,b$分别乘$2$,最后答案除以$2$即可。

代码

/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*its=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==its)
            its=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==its)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        }
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
}
inline void read(int &x){
	int rt = FastIO::getint();
	x = rt;
}
inline void print(int x){
	FastIO::putint(x);
	FastIO::flush();
}
/* definitions */
const int MAXN = 1e4+10;
int n,m,ans;
int poival[MAXN];
/* functions */
inline void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&poival[i]);
        poival[i]<<=1;
    }
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        poival[a]+=c;
        poival[b]+=c;
    }
}
inline void work(){
    std::sort(poival+1,poival+n+1);
    while(n){
        ans=ans+(poival[n--]-poival[n--]);
    }
    ans/=2;
    printf("%d\n",ans);
}
int main(int argc,char *argv[]){
	init();
    work();
	return 0;
}

洛谷P4643「国家集训队」题解