M_sea

洛谷4643 [国家集训队]阿狸和桃子的游戏
LuoguBZOJ分析代码只比概率论长一点的黑题...发现这个边权不太好搞,于是考虑化成点权。如果有一条边$(u,...
扫描右侧二维码阅读全文
31
2019/01

洛谷4643 [国家集训队]阿狸和桃子的游戏

Luogu

BZOJ

分析

代码只比概率论长一点的黑题...

发现这个边权不太好搞,于是考虑化成点权。

如果有一条边$(u,v,w)$,那么将$u$的点权增加$w/2$,将$v$的点权增加$w/2$。

正确性?分情况讨论:

  • 如果$\text{A}$同时染了$u$和$v$,那么它还是可以得到$w$。
  • 如果$\text{A}$染了$u$,$\text{B}$染了$v$,那么它们都多得了$w/2$,差不变。

这样之后,显然可以贪心地选,每次染点权大的点。

然后,为了避免浮点数,可以将所有数据乘$2$再运算,最后结果除以$2$。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000+10;

int n,m,ans;
int val[N];
inline int cmp(int x,int y) { return x>y; }

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) val[i]=read()<<1;
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read(),w=read();
        val[u]+=w,val[v]+=w;
    }
    sort(val+1,val+n+1,cmp);
    for (re int i=1;i<=n;i+=2) ans+=val[i]-val[i+1];
    printf("%d\n",ans>>1);
    return 0;
}
最后修改:2019 年 05 月 26 日 08 : 10 PM

发表评论