P4643-[国家集训队]阿狸和桃子的游戏【结论】
2024-08-31 10:59:14
正题
题目链接:https://www.luogu.com.cn/problem/P4643
题目大意
给出\(n\)个点\(m\)条边的无向图,两个人轮流选择一个未被选择的点加入点集。
然后每个人的权值为选出的点的导出子图点权加边权和。
两个人都希望自己的权值减去对方的权值最大
求先手的权值减去后手的权值
\(1\leq n\leq 10^4,1\leq m\leq 10^5\)
解题思路
结论就是把边权均分到点权处。
证明的话假设两个点之间的点权为\(w\)。
那么如果两边颜色不同那么这个均分出来的权值会统计一个\(\frac{w}{2}-\frac{w}{2}=0\)的权值
如果两边颜色相同那么就会统计上这个权值。排序然后一个一个选就好了
时间复杂度\(O(n\log n+m)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,m,w[N],v[N],p[N],x[N],y[N],e[N],ans;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]),v[i]=w[i]*2,p[i]=i;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x[i],&y[i],&e[i]);
v[x[i]]+=e[i];v[y[i]]+=e[i];
}
sort(v+1,v+1+n);
for(int i=n;i>=1;i-=2)
ans+=v[i]-v[i-1];
printf("%d\n",ans/2);
return 0;
}
最新文章
- poj 3264
- effective OC2.0 52阅读笔记(二 对象、消息、运行期)
- 如何查看设备的 UDID
- 设置sublime text2/3中默认预览浏览器快捷键的方法
- iphone--有关日历中NSDateFormatter中英文
- HTTP有关知识
- pyqt5实现注册界面并获得文本框内容
- 13.Git分支-变基(rebase)、rebase VS merge
- ubuntu 下安装docker 踩坑记录
- Tesseract--主要API功能介绍
- mac xmind 激活
- python黑帽子-黑客与渗透测试编程之道(源代码)
- 在 ASP.NET CORE 中使用 SESSION (转载)
- SharePoint Designer 配置工作流后需要重启的问题
- css3 animation(动画)笔记
- 四边形优化dp
- windows200364位iis6 php环境搭建
- Ubuntu下利用vim搭建python开发环境
- 再也不学AJAX了!(一)AJAX概述
- Unity3d中SendMessage 用法