BZOJ2115: [Wc2011] Xor(线性基)

Time Limit: 10 Sec  Memory Limit: 259 MB

Submit: 4848  Solved: 2030

[Submit][Status][Discuss]

Description

Input

第一行包含两个整数N和 M, 表示该无向图中点的数目与边的数目。 接下来M 行描述 M 条边,每行三个整数Si,Ti ,Di,表示 Si 与Ti之间存在 一条权值为 Di的无向边。 图中可能有重边或自环。

Output

仅包含一个整数,表示最大的XOR和(十进制结果),注意输出后加换行回车。

Sample Input

5 7 1 2 2 1 3 2 2 4 1 2 5 1 4 5 3 5 3 4 4 3 2

Sample Output

6

HINT

Source

感觉std的思路比较套路

首先我们求出任意一条路径的xor值

然后我们假设有另外一条路径的xor值比当前优,我们考虑如何把当前路径一步步替换为最优路径

有两种情况

1:当前路径和最优路径不存在交集,那么这两条路径构成一个环

2:当前路径和最优路径存在交集,那么这两条路径的并 中会出现一些环,我们只需要把当前路径在环上的部分替换掉就好

因此,不论哪种情况,我们都需要找到异或和最大的环

然后dfs一边找出所有环,扔到线性基里求最大值就好了。。

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long 
using namespace std;
const int MAXN = 2 * 1e5 + 10,  B = 62;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M;
struct Edge {
    int u, v, w, nxt;
}E[MAXN];
int head[MAXN], num = 1;
inline void AddEdge(int x, int y, int z) {
    E[num] = (Edge) {x, y, z, head[x]};
    head[x] = num++;
}
int vis[MAXN], P[MAXN], dis[MAXN];
void Insert(int x) {
    for(int i = B; i >= 0; i--) {
        if((x >> i) & 1) {
            if(!P[i]) {P[i] = x; return ;}
            x = x ^ P[i];
        }
    }
}
void FindQuan(int x, int fa) {
    vis[x] = 1;
    for(int i = head[x], v; i != -1; i = E[i].nxt) {
        if((v = E[i].v) == fa) continue;
        if(vis[v]) {Insert(dis[x] ^ dis[v] ^ E[i].w); continue;}
        dis[v] = dis[x] ^ E[i].w;
        FindQuan(v, x);
    }
}
main() { 
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif
    memset(head, -1, sizeof(head));
    N = read(); M = read();
    for(int i = 1; i <= M; i++) {
        int x = read(), y = read(), z = read();
        AddEdge(x, y, z); AddEdge(y, x, z);
    }
    FindQuan(1, 0);
    int ans = dis[N];
    for(int i = B; i >= 0; i--)
        if((ans ^ P[i]) > ans)
            ans = ans ^ P[i];
    printf("%lld", ans);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[剑指offer] 和为S的连续正数序列

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100...

7710
来自专栏PPV课数据科学社区

Pandas速查卡-Python数据科学

Josh Devlin 2017年2月21日 Pandas可以说是数据科学最重要的Python包。 它不仅提供了很多方法和函数,使得处理数据更容易;而且它已经...

41880
来自专栏HTML5学堂

Javascript中的Label语句

HTML5学堂:在JavaScript中,我们可能很少会去用到 Label 语句,但是熟练的应用 Label 语句,尤其是在嵌套循环中熟练应用 break, c...

43570
来自专栏青玉伏案

iOS开发之Masonry框架源码解析

Masonry是iOS在控件布局中经常使用的一个轻量级框架,Masonry让NSLayoutConstraint使用起来更为简洁。Masonry简化了NSLay...

22780
来自专栏漫漫深度学习路

pytorch学习笔记(七):pytorch hook 和 关于pytorch backward过程的理解

pytorch 的 hook 机制 在看pytorch官方文档的时候,发现在nn.Module部分和Variable部分均有hook的身影。感到很神奇,因为在使...

1.4K50
来自专栏小狼的世界

Leetcode刷题记录:计算复数乘法

11310
来自专栏前端菜鸟变老鸟

判断两个json是不是相等的

21730
来自专栏数值分析与有限元编程

可视化 | 一个三角形常应变单元后处理例子

昨天提到了应力云图,其实质是用不同的颜色填充等值线。有了结点的应力值,单元内任意一点的应力值是通过插值实现的。下面来看一个悬臂梁的综合后处理。 如图所示,一个悬...

29570
来自专栏机器学习从入门到成神

哥伦布编码

哥伦布编码解码 UINT GetUeValue(BYTE *pBuff, UINT nLen, UINT &nStartB...

25020
来自专栏Bingo的深度学习杂货店

Q63 Unique Paths II

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the...

9840

扫码关注云+社区

领取腾讯云代金券