bzoj2115(线性基)

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2115

题意：求图中路径1~n上最大边权 xor 和

思路：参见 blog http://blog.csdn.net/qwb492859377/article/details/52939589

代码：

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #define ll long long
 5 using namespace std;
 6   
 7 const int MAXN = 5e5 + 10;  
 8 const int inf = 0x3f3f3f3f;  
 9   
10 struct Edge {  
11     ll val;  
12     int v, nxt;  
13 } E[MAXN * 2];
14 
15 int head[MAXN], id; 
16 
17 void edge_init() {  
18     id = 0;  
19     memset(head, -1, sizeof(head));  
20 }  
21 
22 void edge_add(int u, int v, ll val) {  
23     E[id].v = v;  
24     E[id].val = val;  
25     E[id].nxt = head[u];  
26     head[u] = id++;  
27 }  
28   
29 int n, m, sz;  
30 ll A[MAXN], P[62], dis[MAXN];  
31 
32 void Guass_base(void) {  
33     memset(P, 0, sizeof(P));  
34     for(int i = 1; i <= sz; i++) {  
35         for(int j = 62; j >= 0; j--) {  
36             if(!(A[i] >> j & 1)) continue;  
37             if(!P[j]) {  
38                 P[j] = A[i]; break;  
39             }  
40             A[i] ^= P[j];  
41         }  
42     }  
43 }  
44 
45 void DFS(int u, ll s) {  
46     if(dis[u] == -1) dis[u] = s;  
47     else {  
48         A[++sz] = s ^ dis[u];  
49         return;  
50     }  
51     for(int i = head[u]; ~i; i = E[i].nxt) {  
52         int v = E[i].v;  
53         DFS(v, s ^ E[i].val);  
54     }  
55 }  
56   
57 int main(void) {  
58     while(~scanf("%d%d", &n, &m)) {  
59         sz = 0;  
60         edge_init();  
61         memset(dis, -1, sizeof(dis));  
62         for(int i = 1; i <= m; i++) {  
63             int u, v; 
64             ll val;  
65             scanf("%d%d%lld", &u, &v, &val);  
66             edge_add(u, v, val);  
67             edge_add(v, u, val);  
68         }  
69         DFS(1, 0);  
70         Guass_base();  
71         ll ans = dis[n];  
72         for(int i = 62; i >= 0; i--) {  
73             ans = max(ans, ans ^ P[i]);  
74         }  
75         printf("%lld
", ans);  
76     }  
77     return 0;  
78 }

View Code