bzoj 2115 线性基
2024-09-21 11:18:39
这种路径异或问题,可以转换为一条路径和若干个环的线性组合,然后就能用线性基搞了。
复习了一波线性基。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PII pair<int, int>
#define PLI pair<LL, int>
#define ull unsigned long long
using namespace std; const int N = 1e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ; int n, m;
LL d[N];
bool vis[N];
vector<PLI> edge[N];
struct Base {
vector<LL> a;
void add(LL x) {
for(int i = ; i < a.size(); i++)
x = min(x, x^a[i]);
if(!x) return;
for(int i = ; i < a.size(); i++)
a[i] = min(a[i], a[i]^x);
a.push_back(x);
}
LL getMx(LL ans) {
for(int i = ; i < a.size(); i++)
ans = max(ans, ans^a[i]);
return ans;
}
} base; void dfs(int u, int fa) {
vis[u] = true;
for(int i = ; i < edge[u].size(); i++) {
int v = edge[u][i].se; LL w = edge[u][i].fi;
if(v == fa) continue;
if(vis[v]) {
base.add(d[u]^d[v]^w);
} else {
d[v] = d[u] ^ w;
dfs(v, u);
}
}
}
int main() {
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++) {
int u, v; LL w;
scanf("%d%d%lld", &u, &v, &w);
edge[u].push_back(mk(w, v));
edge[v].push_back(mk(w, u));
}
dfs(, );
printf("%lld\n", base.getMx(d[n]));
return ;
} /*
*/
最新文章
- 做的一个HTML表白页面
- CSS之border-radius
- C# UdpClient 设置超时时间
- Tomcat配置虚拟主机后的登录验证码问题
- 测试web数据库的分布式事务atomikos 的三种数据源 SimpleDataSourceBean,AtomikosDataSourceBean,AtomikosNonXADataSourceBean
- hadoop的ganglia数据监控
- Delphi XE5教程8:使用Delphi命名空间
- jquery的select元素和option的相关操作
- delphi中DLL编程详解
- Ling to entity实现分页
- 2017《JAVA技术预备作业》 1502 陈明宇
- 1049. Counting Ones (30)
- Apollo与ROS
- Go语言--数组、切片、
- angular简介
- 【先验知识归纳】Flask快速入门
- 合并hive/hdfs小文件
- 20175314薛勐 MyCP(课下作业,必做)
- python3之MongoDB
- e837. 设置JTabbedPane中卡片的颜色