首页 > 其他 > 详细

BZOJ 2115: [Wc2011] Xor

时间:2017-03-21 10:07:32      阅读:238      评论:0      收藏:0      [点我收藏+]

2115: [Wc2011] Xor

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 3096  Solved: 1321
[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

 

技术分享

 

想法:
  技术分享 
画一张比较乱的图,再勾出一圈圈路径,然后标明那些边被xor奇数次。就会发现一条S-T简单路径,若干个(边)不相交的环。
然后理性分析一下:
先走一条S-T的简单路径L。
①对于原图上任何一个不与L(边)相交环,都可以通过绕两次得到,并消去走过与回来的路径。是一个合法的行走路线。
②一个与L相交的环,都可以消去L上一段连续的路径,进而成为新的S-T的简单路径L‘,同样也是合法行走路线。
③上述环要求互不相交,对于两个相交的环,可以消去相交部分,进而得到一个大环。也是合法行走路线
于是,得到对于图中任何一条S-T的简单路径和若干的小环之间的组合,就可以xor出所有S-T的路径的xor值。
因为这是一张无向连通图,只需DFS一遍,返祖边与树边构成的便是小环,并且可以得到所有小环xor值。
题目转变成:给你数集{S},再给一个数x,要求x与{S}的子集的xor值最大。 线性基解决。
 
总复杂度DFS+线性基O(m*62).
 
 1 #include<cstdio>
 2 #define ll long long
 3 const int lem(100000),len(50000);
 4 struct Node{int nd,nx;ll co;}bot[lem*2+10];
 5 int tot,first[len+10],vist[len+10];
 6 int n,m,a,b;ll dis[len+10],back,c;
 7 ll max(ll a,ll b){return a>b?a:b;}
 8 struct Linear_Base
 9 {
10     ll p[63];
11     void ins(ll x)
12     {
13         for(int j=62;j>=0;j--)
14         if((x>>j)&1)
15         {
16             if(p[j])x^=p[j];
17             else {p[j]=x;break;}
18         }
19     }
20     ll same(ll x)
21     {
22         ll res=x;
23         for(int j=62;j>=0;j--)
24         res=max(res,res^p[j]);
25         return res;
26     }
27 }A;
28 void add(int a,int b,ll c){bot[++tot]=(Node){b,first[a],c};first[a]=tot;}
29 void dfs(int x)
30 {
31     vist[x]=1;
32     for(int v=first[x];v;v=bot[v].nx)
33     {
34         if(vist[bot[v].nd])
35             A.ins(dis[bot[v].nd]^dis[x]^bot[v].co);//xor小环 
36         else 
37         {
38             dis[bot[v].nd]=dis[x]^bot[v].co;
39             dfs(bot[v].nd);
40         }
41     }
42 }
43 int main()
44 {
45     scanf("%d%d",&n,&m);
46     for(int i=1;i<=m;i++)
47     {
48         scanf("%d%d%lld",&a,&b,&c);
49         add(a,b,c);add(b,a,c);
50     }
51     dfs(1);
52     printf("%lld\n",A.same(dis[n]));//需要钦点S-T的路径有出现过 
53     return 0;
54 }

 

BZOJ 2115: [Wc2011] Xor

原文:http://www.cnblogs.com/Oncle-Ha/p/6592604.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!