BZOJ-2563: 阿狸和桃子的游戏

[文章目录]

Description

阿狸和桃子正在玩一个游戏,游戏是在一个带权图G=(V, E)上进行的,设节点权值为w(v),边权为c(e)。游戏规则是这样的:
  1. 阿狸和桃子轮流将图中的顶点染色,阿狸会将顶点染成红色,桃子会将顶点染成粉色。已经被染过色的点不能再染了,而且每一轮都必须给一个且仅一个顶点染色。
  2. 为了保证公平性,节点的个数N为偶数。
  3. 经过N/2轮游戏之后,两人都得到了一个顶点集合。对于顶点集合S,得分计算方式为

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

由于求最大分数相减,得分虑将边上的代价转移到点上。如果一条边两端点不属于同一个人,说明这条边对两点不做贡献。如果属于同一个点,那么贡献为c。
那就可以将边权均分到端点上。
如果c为奇数???直接代价都翻倍,然后ans除以2就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,w[11000];
long long ans;
bool cmp(int x,int y){return x>y;}
int main()
{
    scanf("%d%d",&n,&m);
    int x,y,z,i;
    for(i=1;i<=n;++i) scanf("%d",w+i),w[i]<<=1;
    while(m--)
    {
        scanf("%d%d%d",&x,&y,&z);
        w[x]+=z; w[y]+=z;
    }
    sort(w+1,w+n+1,cmp);
    for(i=1;i<=n;++i)
    {
        if(i&1) ans+=w[i];
        else ans-=w[i];
    }
    printf("%lld",ans>>1);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注