当前位置: 首页 > news >正文

牛客练习赛114 G-图上异或难题(线性基)

题目要求把点涂成白和黑两种颜色,如果一条边左右两端是不同的颜色的话,结果就异或这跳边的权值,求结果最大是多少

把边的贡献转换成点的贡献

我们只考虑白色点的情况下,如果一个点A是白色,就把结果异或上这一个点A周围的所有边,

如果在该点周围还有一个白色点B的话,那么我们同样把结果异或上这个点B的所有边

因为我们知道两个点是有线段相连,而且两个点都异或上该点周围的所有边了

所以两个点相邻的线段就被去掉了

其他点同理

这时候我们就可以把这个问题转换成一个线性基的问题

已知所以点的贡献是该点异或上周围所有边

求从n个点中选出一部分点染成白色的最大异或和

const int inf = 0x3f3f3f3f3f3f3f3f, N = 2e5 + 5, mod = 1e9 + 7;
vector<int>q[N];
int a[N];
signed main()
{ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);int T;cin >> T;while (T--){int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {q[i].clear(); a[i] = 0;}while (m--){int u, v, w;cin >> u >> v >> w;q[u].push_back(w);q[v].push_back(w);}for (int i = 1; i <= n; i++) {for (auto w : q[i]){a[i] ^= w;}}int k = 1;for (int i = 32; i >= 0; i--){for (int j = k; j <= n; j++) {if (a[j] >> i & 1) {swap(a[j], a[k]);break;}}if (!(a[k] >> i & 1)) continue;for (int j = 1; j <= n; j++) {if (j != k && (a[j] >> i & 1))a[j] ^= a[k];}k++;if (k == n + 1) break;}int res = 0;for (int i = 1; i <= k; i++) {res ^= a[i];}cout << res << "\n";}
}

http://www.lryc.cn/news/140624.html

相关文章:

  • Neo4j之ORDER BY基础
  • 【C++杂货铺】探索vector的底层实现
  • MybatisPlus(1)
  • 探索未来世界,解密区块链奥秘!
  • win10 下运行 npm run watch-poll问题
  • Android平台RTMP|RTSP直播播放器功能进阶探讨
  • Centos7安装Telnet服务
  • 【C++】GCC对应C++的版本支持
  • 前端面试:【算法】排序、查找、递归、动态规划
  • RK3399 开机自启一个shell脚本,一直起不来BUG
  • [MyBatis系列④]核心配置文件
  • 系统架构设计高级技能 · 层次式架构设计理论与实践
  • Nuxt3打包部署到Linux(node+pm2安装和运行步骤+nginx代理)
  • 一维数组传参
  • 七层、四层和五层网络模型区别和联系
  • RH1288V3 - 初识物理服务器
  • excel中如果A列中某项有多条记录,针对A列中相同的项,将B列值进行相加合并统计
  • 开发智能应用的新范式:大数据、AI和云原生如何构建智能软件
  • 淘宝免费爬虫数据 商品详情数据 商品销售额销量API
  • Markdown初级使用指南
  • 国际版阿里云/腾讯云CDN装备运用教程:加快网站拜访速度
  • 面试之快速学习计算机网络-http
  • 2023水果编曲软件fl studio 21.1.0 .3713官方中文直装破解版
  • 【微信小程序】页面路由跳转函数之间的区别
  • Ubuntu inotify
  • 开始MySQL之路——MySQL的DataGrip图形化界面
  • C++ STL 标准模板库
  • C#-集合小例子
  • git保存删除的文件
  • 【golang】go语句执行规则(goroutine)(下)