【bzoj2563】阿狸和桃子的游戏 贪心
2024-08-31 12:04:57
题目描述
阿狸和桃子正在玩一个游戏,游戏是在一个带权图G=(V, E)上进行的,设节点权值为w(v),边权为c(e)。游戏规则是这样的:
1. 阿狸和桃子轮流将图中的顶点染色,阿狸会将顶点染成红色,桃子会将顶点染成粉色。已经被染过色的点不能再染了,而且每一轮都必须给一个且仅一个顶点染色。
2. 为了保证公平性,节点的个数N为偶数。
3. 经过N/2轮游戏之后,两人都得到了一个顶点集合。对于顶点集合S,得分计算方式为
由于阿狸石头剪子布输给了桃子,所以桃子先染色。两人都想要使自己的分数比对方多,且多得越多越好。如果两人都是采用最优策略的,求最终桃子的分数减去阿狸的分数。
1. 阿狸和桃子轮流将图中的顶点染色,阿狸会将顶点染成红色,桃子会将顶点染成粉色。已经被染过色的点不能再染了,而且每一轮都必须给一个且仅一个顶点染色。
2. 为了保证公平性,节点的个数N为偶数。
3. 经过N/2轮游戏之后,两人都得到了一个顶点集合。对于顶点集合S,得分计算方式为
由于阿狸石头剪子布输给了桃子,所以桃子先染色。两人都想要使自己的分数比对方多,且多得越多越好。如果两人都是采用最优策略的,求最终桃子的分数减去阿狸的分数。
输入
输入第一行包含两个正整数N和M,分别表示图G的节点数和边数,保证N一定是偶数。
接下来N+M行。
前N行,每行一个整数w,其中第k行为节点k的权值。
后M行,每行三个用空格隔开的整数a b c,表示一条连接节点a和节点b的边,权值为c。
输出
输出仅包含一个整数,为桃子的得分减去阿狸的得分。
样例输入
4 4
6
4
-1
-2
1 2 1
2 3 6
3 4 3
1 4 5
样例输出
3
题解
贪心
考虑对自己得分-对手得分的贡献,一个点选的贡献为w,不选的贡献为-w;一条边两个端点都不选的贡献为-c,选一个的贡献为0,选两个的贡献为c。
那么相对于不选,选择一个点的贡献为2*w,选择某条边的一个端点的贡献为c。
于是把点权赋为2*原点权-所有与它相连的边的边权和,两人轮流取最大即可。
最后的结果需要除以2,因为每个点和每条边计算了两次。
#include <cstdio>
#include <algorithm>
using namespace std;
int v[10010];
int main()
{
int n , m , i , x , y , z , ans = 0;
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &v[i]) , v[i] <<= 1;
for(i = 1 ; i <= m ; i ++ ) scanf("%d%d%d" , &x , &y , &z) , v[x] += z , v[y] += z;
sort(v + 1 , v + n + 1);
for(i = n ; i >= 1 ; i -- )
{
if((n - i) & 1) ans -= v[i];
else ans += v[i];
}
printf("%d\n" , ans >> 1);
return 0;
}
最新文章
- OSX下Python模块安装常见问题解决
- allegro - 层叠相关参数
- Java程序员的日常—— POI与JDBC、Mockmvc与单元测试
- [原创]cocos2d-x研习录-第二阶 概念类之导演类(CCDirector)
- WCF 下载“http://localhost:XXX”时出错。无法连接到远程服务器。由于目标计算机积极拒绝,无法连接。
- discuz分类信息地区联动菜单字段
- Android开发之自定义圆角矩形图片ImageView的实现
- order by跟group by 跟having----------------sum() 求和 avg()求平均 count() 求个数--------------like
- php 总结
- Service、Alarm与BroadcastReceiver的使用方法
- 在线用户管理--ESFramework 4.0 进阶(05)
- <;url-pattern>;/<;/url-pattern>;和<;url-pattern>;/*<;/url-pattern>;区别
- Sqoop工具
- iOS下JS与OC互相调用(三)--MessageHandler
- darknet训练yolov3时的一些注意事项
- 转:更改SQLServer实例默认字符集
- idea 控制台行数限制
- webapck html-loader实现资源复用
- hibernate中3个重要的类 Configuration SessionFactory Session
- 多线程之并发容器ConcurrentHashMap
热门文章
- HDU 4283 You Are the One (区间DP,经典)
- LeetCode Pascal&#39;s Triangle Pascal三角形
- Spring Mybatis PageHelper 设置使用
- ucos-ii核心算法分析(转)
- 面试题-谈谈你对Java平台的理解
- 阻止form元素内的input标签回车提交表单
- 虚拟机设置NAT
- Find the Longest Word in a String-freecodecamp算法题目
- tensorflow目标检测API之训练自己的数据集
- 【思维题 集合hash 树上差分】11.5撸树