bzoj2115【WC2001】Xor

By | 04月07日
Advertisement

2115: [Wc2011] Xor

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 2059 Solved: 856
[Submit][Status][Discuss]

Description

bzoj2115【WC2001】Xor

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

bzoj2115【WC2001】Xor

贪心+线性基(什么是线性基...我只知道宋仲基2333)

有一个性质,一个数被异或两次就等于0,所以一条边在路径中出现偶数次就会被抵消。那么我们就可以随便找一条1到n的路径,然后把它异或一些简单环,就可以得到其他路径。

现在我们要找出无向图中的所有简单环,DFS的过程中加一些判断就可以了。

于是问题就变成从一个数组中找几个数,让他们和另一个数的异或和最大。方法是对于这个数组求线性基,然后在线性基里倒着贪心。(详见代码)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 50005
#define maxm 200005
using namespace std;
int n,m,cnt,tot,head[maxn];
ll ans,d[maxn],a[maxm],b[100];
bool vst[maxn];
struct edge_type{int next,to;ll w;}e[maxm];
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void add_edge(int x,int y,ll w)
{
    e[++cnt]=(edge_type){head[x],y,w};head[x]=cnt;
    e[++cnt]=(edge_type){head[y],x,w};head[y]=cnt;
}
inline void dfs(int x)
{
    vst[x]=true;
    for(int i=head[x];i;i=e[i].next)
    {
        int y=e[i].to;
        if (!vst[y])
        {
            d[y]=d[x]^e[i].w;
            dfs(y);
        }
        else a[++tot]=d[x]^d[y]^e[i].w;
    }
}
int main()
{
    n=read();m=read();
    F(i,1,m)
    {
        int x=read(),y=read();ll z=read();
        add_edge(x,y,z);
    }
    dfs(1);
    ans=d[n];
    F(i,1,tot) D(j,63,0) if ((a[i]>>j)&1)
    {
        if (!b[j]){b[j]=a[i];break;}
        else a[i]^=b[j];
    }
    D(i,63,0) if (b[i]&&((ans>>i)&1)==0) ans^=b[i];
    printf("%lld\n",ans);
    return 0;
}

Similar Posts:

  • 【CodeChef-XRQRS】Xor Queries【可持久化Trie / +主席树】

    [题目链接] 有中文题面就不发题意了. 似乎维护一个可持久化Trie和一个主席树就可以做了,但是仔细想想好像只需要一个可持久化Trie就完了. 脑补了一下Trie上找第k大和统计数个数,似乎是对了. 1A了.. /* Pigonometry */ #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 500005, maxk = 21

  • 【HDU3949】XOR——线性基

    Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description XOR is a kind of bit operator, we define that as follow: for two binary base number A and B, let C=A XOR B, then for each bit of C, we can get its va

  • 【翻译】(72)硬件加速

    [翻译](72)硬件加速 see http://developer.android.com/guide/topics/graphics/hardware-accel.html 原文见 http://developer.android.com/guide/topics/graphics/hardware-accel.html ------------------------------- Hardware Acceleration 硬件加速 ----------------------------

  • 【原创】破解光影魔术手0.24注册机(VB)源代码

    [原创]通过编译,运行环境WINXP HOME + VB 做人要厚道,转贴请注明出处. 声明:仅供学习交流使用,光影魔术手版本0.24 Private Const NCBASTAT = &H33 Private Const NCBNAMSZ = 16 Private Const HEAP_ZERO_MEMORY = &H8 Private Const HEAP_GENERATE_EXCEPTIONS = &H4 Private Const NCBRESET = &H32 D

  • 【翻译】Qt内部机制及逆向

    标 题: [翻译]Qt内部机制及逆向 作 者: zouzhin 时 间: 2011-04-30,15:51:44 链 接: http://bbs.pediy.com/showthread.php?t=133181 [翻译]Qt内部机制及逆向 原作者:Daniel Pistelli : 翻 译:zouzhin 参加看雪有很长一段时间了,一直无所贡献,真是有愧各位同坛好友.前不久发了个Qt求助帖http://bbs.pediy.com/showthread.php?t=132491,没人回复,刚好看

  • 【转载】乱解 API 函数 -- API 绝密档案系列之二

    转自:http://bbs.pediy.com/showthread.php?s=&threadid=22231 标 题: [原创]乱解 API 函数 -- API 绝密档案系列之二 作 者: gzgzlxg 时 间: 2006-03-07,06:45 链 接: http://bbs.pediy.com/showthread.php?t=22231 乱解 API 函数 -- API 绝密档案系列之二 通向高手之路 上一篇介绍了两个结构,今后你会发现,在系统程序中,对这两个结构的引用无所不在,理解

  • 【原创】Windows X64汇编入门(1)

    标 题: [原创]Windows X64汇编入门(1) 作 者: tankaiha 时 间: 2007-05-05,23:31:26 链 接: http://bbs.pediy.com/showthread.php?t=43967 Windows X64汇编入门(1) tankaiha 最近断断续续接触了些64位汇编的知识,这里小结一下,一是阶段学习的回顾,二是希望对64位汇编新手有所帮助.我也是刚接触这方面知识,文中肯定有错误之处,大家多指正. 文章的标题包含了本文的四方面主要内容: (1)W

  • 【原创】shadow ssdt学习笔记(一)(二)

    http://bbs.pediy.com/showthread.php?t=56955 标 题: [原创]shadow ssdt学习笔记(一)(二) 作 者: zhuwg 时 间: 2007-12-22,22:01:29 链 接: http://bbs.pediy.com/showthread.php?t=56955 1.取得shadow ssdt真实地址 系统只提供了KeServiceDescriptorTable导出 KeServiceDescriptorTableShadow是个未导出结构

  • 【原创】rootkit ring3进ring0之门系列[三] -- 任务门

    标 题: [原创]rootkit ring3进ring0之门系列[三] -- 任务门 作 者: combojiang 时 间: 2008-04-04,19:39:51 链 接: http://bbs.pediy.com/showthread.php?t=62510 今天我们一起学习下任务门.为了便于理解原理,首先来看几个数据结构. 处理器为了处理任务,定义了5个相关的数据结构. 1) Task-state segment (TSS) 2) TSS descriptor 3) Task-gate

  • 【零】解题报告

    2.零 [问题描述] 零是个好数字啊.万物都是从0开始的,譬如说c语言的数组下标,你在世界上存在的天数啊等等等等,然后一个数xor它自己结果也是等于0的.根据惯例,我们的第一句话一定与题目无关的. 其实题目还是很简单,求出给出的若干个数的乘积末尾有多少个0. . [输入文件] 输入文件zero.in.第一行包含一个整数n,代表乘数的个数.接下来n行分别是n个正整数,行首行尾行中均不会有空格出现,出现找我算账. [输出文件] 输出文件zero.out应包含一个正整数,为乘积末尾0的个数. [样例输

Tags: