首页 > 其他 > 详细

BZOJ2115: [Wc2011] Xor(Dfs树,Xor线性无关组)

时间:2019-01-18 00:31:43      阅读:65      评论:0      收藏:0      [点我收藏+]

标签:scanf   turn   思路   就是   eof   现在   异或和   tps   order   

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

技术分享图片

解题思路:

神题!!!

就是说发现如果存在简单路径最大,那么一定会采取,而且不会蹭来蹭去的因为会被异或掉是徒劳的。

现在考虑一个问题:这条路径可不可以被拓展呢。

好像是可以的,而且只能这样拓展:走到一个环,然后原路返回。

这样就只需要Dfs树一遍,将非树边更新至线性无关组里,

最后查最大异或和就好了。

代码:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 typedef long long lnt;
 5 struct pnt{
 6     int hd;
 7     lnt dis;
 8     bool vis;
 9 }p[100000];
10 struct ent{
11     int twd;
12     int lst;
13     lnt vls;
14 }e[1000000];
15 int cnt;
16 int n,m;
17 lnt b[70];
18 void ade(int f,int t,lnt v)
19 {
20     cnt++;
21     e[cnt].twd=t;
22     e[cnt].vls=v;
23     e[cnt].lst=p[f].hd;
24     p[f].hd=cnt;
25     return ;
26 }
27 bool Insert(lnt x)
28 {
29     for(int i=62;i>=0;i--)
30     {
31         if(x&(1ll<<i))
32         {
33             if(b[i]==-1)
34             {
35                 b[i]=x;
36                 return true;
37             }else x^=b[i];
38         }
39     }
40     return false;
41 }
42 lnt Query(lnt x_)
43 {
44     for(int i=62;i>=0;i--)
45         x_=std::max(x_,x_^b[i]);
46     return x_;
47 }
48 void Dfs(int x_)
49 {
50     p[x_].vis=true;
51     for(int i=p[x_].hd;i;i=e[i].lst)
52     {
53         int t_=e[i].twd;
54         if(p[t_].vis)Insert(p[t_].dis^p[x_].dis^e[i].vls);
55         else{
56             p[t_].dis=p[x_].dis^e[i].vls;
57             Dfs(t_);
58         }
59     }
60     return ;
61 }
62 int main()
63 {
64     memset(b,-1,sizeof(b));
65     scanf("%d%d",&n,&m);
66     for(int i=1;i<=m;i++)
67     {
68         int x,y;
69         lnt c;
70         scanf("%d%d%lld",&x,&y,&c);
71         ade(x,y,c),ade(y,x,c);
72     }
73     Dfs(1);
74     printf("%lld\n",Query(p[n].dis));
75     return 0;
76 }

 

BZOJ2115: [Wc2011] Xor(Dfs树,Xor线性无关组)

标签:scanf   turn   思路   就是   eof   现在   异或和   tps   order   

原文:https://www.cnblogs.com/blog-Dr-J/p/10285402.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 designnerd.net 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号