第一行包含两个整数N和 M, 表示该无向图中点的数目与边的数目。 接下来M 行描述 M 条边,每行三个整数Si,Ti ,Di,表示 Si 与Ti之间存在 一条权值为 Di的无向边。 图中可能有重边或自环。
仅包含一个整数,表示最大的XOR和(十进制结果),注意输出后加换行回车。
想法:
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 }
原文:http://www.cnblogs.com/Oncle-Ha/p/6592604.html