2115: [Wc2011] Xor
2024-08-24 07:45:29
2115: [Wc2011] Xor
分析:
对于图中的一个环,是可以从1到这个环,转一圈然后在回到1的,所以可以一开始走很多个环,然后在走一条1到n的路径。
那么可以求出所有的环,加入到线性基中,然后任意一条1->n的路径,取一遍最大值。
如果1->n的路径就是最终要走的路径,那么就取到了。如果不是,这我们走的这条路径是p1,最终答案最大的路径是p2,那么p1和p2合起来就是个环,如果p2更优和这个环异或,就把p1消掉了。
代码:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL; inline LL read() {
LL x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = ;
struct Edge{ int to, nxt; LL w; } e[N * ];
int head[N], En;
LL dis[N], b[N];
bool vis[N];
vector<LL> cir; inline void add_edge(int u,int v,LL w) {
++En; e[En].to = v, e[En].w = w, e[En].nxt = head[u]; head[u] = En;
}
void dfs(int u) {
vis[u] = ;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (vis[v]) {
cir.push_back(dis[u] ^ e[i].w ^ dis[v]);
}
else {
dis[v] = dis[u] ^ e[i].w;
dfs(v);
}
}
}
void Insert(LL x) {
for (int i = ; ~i; --i)
if ((x >> i) & ) {
if (b[i]) x ^= b[i];
else {
b[i] = x; break;
}
}
}
int main() {
int n = read(), m = read();
for (int i = ; i <= m; ++i) {
int u = read(), v = read(); LL w = read();
add_edge(u, v, w);
}
dfs();
for (int i = ; i < (int)cir.size(); ++i) Insert(cir[i]);
LL ans = dis[n];
for (int i = ; ~i; --i)
if (ans < (ans ^ b[i])) ans = ans ^ b[i];
cout << ans;
return ;
}
最新文章
- XML学习笔记2——DTD
- 详尽介绍FireFox about:config
- XX.frame.origin.x 赋值问题
- 用PHP生成随机数的函数
- 对于android拦截短信的一些疑问
- 自定义View的封装
- 我觉得主要靠积累,难度不是问题,主要靠时间积累,以及兴趣带来的学习能力(我觉得至少5年全职Qt开发经验,才能算精通)
- Fluentd: Open Source Log Management
- 第02周-Java作业评价
- 【mongodb系统学习之七】mongodb的关闭
- hdu 2865 Polya计数+(矩阵 or 找规律 求C)
- Django项目结构介绍
- JPA + SpringData 操作数据库--Helloworld实例
- 【学习笔记】分类算法-k近邻算法
- 一致性hash的实现
- Flash:使用FileReference上传在Firefox上遇到的问题终于解决了
- ES6通过使用babel兼容到ie9
- JS省市区联动效果
- VB中的正则表达式
- Redis 备份数据的两种方式
热门文章
- 如何制作 Objective-C 的UML图 [2]
- [UI] 精美UI界面欣赏[7]
- Hybris阶段总结(2)hybris架构
- matlab中关于函数句柄、feval函数以及inline函数的解析 (转)
- Cloudstack
- (1)StringBuilder类和StringBuffer类 (2)日期相关的类 (3)集合框架 (4)List集合
- for 与forEach的区别
- JS&#21644;css&#23454;&#29616;&#26816;&#27979;&#31227;&#21160;&#35774;&#22791;&#26041;&#21521;&#30340;&#21464;&#21270;&#24182;&#21028;&#26029;&#27178;&#31446;&#23631;&#24149;
- SQLServer------遍历操作,游标的基础使用
- 3种web会话管理方式