网站手机源码,免费虚拟主机空间互联,漳州网站建设去博大a优,织梦网站有会员系统怎么做正题
题目链接:https://www.luogu.com.cn/problem/P4643 题目大意
给出nnn个点mmm条边的无向图#xff0c;两个人轮流选择一个未被选择的点加入点集。
然后每个人的权值为选出的点的导出子图点权加边权和。
两个人都希望自己的权值减去对方的权值最大
求先手的权值减去后…正题
题目链接:https://www.luogu.com.cn/problem/P4643 题目大意
给出nnn个点mmm条边的无向图两个人轮流选择一个未被选择的点加入点集。
然后每个人的权值为选出的点的导出子图点权加边权和。
两个人都希望自己的权值减去对方的权值最大
求先手的权值减去后手的权值
1≤n≤104,1≤m≤1051\leq n\leq 10^4,1\leq m\leq 10^51≤n≤104,1≤m≤105 解题思路
结论就是把边权均分到点权处。
证明的话假设两个点之间的点权为www。
那么如果两边颜色不同那么这个均分出来的权值会统计一个w2−w20\frac{w}{2}-\frac{w}{2}02w−2w0的权值
如果两边颜色相同那么就会统计上这个权值。排序然后一个一个选就好了
时间复杂度O(nlognm)O(n\log nm)O(nlognm) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e510;
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 i1;in;i)scanf(%d,w[i]),v[i]w[i]*2,p[i]i;for(int i1;im;i){scanf(%d%d%d,x[i],y[i],e[i]);v[x[i]]e[i];v[y[i]]e[i];}sort(v1,v1n);for(int in;i1;i-2)ansv[i]-v[i-1];printf(%d\n,ans/2);return 0;
}
