Description

Input

第一行包含兩個(gè)整數(shù)N和 M， 表示該無向圖中點(diǎn)的數(shù)目與邊的數(shù)目。 接下來M 行描述 M 條邊，每行三個(gè)整數(shù)Si，Ti ，Di，表示 Si 與Ti之間存在 一條權(quán)值為 Di的無向邊。 圖中可能有重邊或自環(huán)。

Output

僅包含一個(gè)整數(shù)，表示最大的XOR和（十進(jìn)制結(jié)果）,注意輸出后加換行回車。

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

題解

我們考慮如何得到答案，首先所有的環(huán)都是可以經(jīng)過的。這是為什么呢？

假設(shè)我們從$1$號(hào)點(diǎn)開始走，走到一個(gè)環(huán)的起點(diǎn)，然后我們經(jīng)過這個(gè)環(huán)以后回到了環(huán)的起點(diǎn)，這時(shí)我們可以直接回到起點(diǎn)。這樣，除了環(huán)上的路徑，其他的路徑都被抵消了。那么我們就只選了了這個(gè)環(huán)，也就是說，任意一個(gè)環(huán)都是可以選的。

然后我們先把所有的環(huán)都選出來，選入線性基中，再選出任意一條從$1$到$n$的路徑，作為初始$ans$。初始$ans$異或線性基的最大值就是我們求的答案。為什么任意選一條路徑也是可行的呢？

我們選了一條路徑以后，如果存在一條更優(yōu)的路徑，那么這兩條路徑肯定是構(gòu)成一個(gè)環(huán)的，會(huì)被選入線性基中。那么我們?cè)儆贸跏嫉?ans$異或一下這個(gè)環(huán)，我們就會(huì)發(fā)現(xiàn)，初始的$ans$被抵消了，二更優(yōu)的那條路徑留了下來。所以，我們選一個(gè)任意的初始$ans$是可行的。

于是這道題的實(shí)現(xiàn)就很明顯了。先找出所有環(huán)，構(gòu)成線性基，然后找出初始$ans$。這兩步顯然是可以$dfs$一遍一起搞的。然后用$ans$去異或線性基。從高位開始往低位異或。如果當(dāng)前$ans$異或這一位的數(shù)能使$ans$變大，那么就異或。最終得到的$ans$就是我們要求的答案。

補(bǔ)充談?wù)剬?duì)取出環(huán)的異或值的理解：

我們記$d[u]$為從根節(jié)點(diǎn)，到$u$節(jié)點(diǎn)這條路徑上的$xor$和，那么假設(shè)我們$dfs$拓展路徑的時(shí)候，我們找到了以前一個(gè)訪問過的點(diǎn)$v$，

那么這里就構(gòu)成了一個(gè)環(huán)，且由于是$dfs$實(shí)現(xiàn)的，很容易知道$d[u]=d[v]⊕w_1⊕w_2⊕...$，$w$為邊權(quán)。

我們記我們插入線性基的元素（環(huán)上的$xor$和）為$x$，$x=w_1⊕w_2⊕...⊕w_i$，

因?yàn)槲覀冎?a⊕a=0$，那么$x=d[u]⊕d[u]⊕w_1⊕w_2⊕...⊕w_i$$=d[u]⊕d[v]⊕w_i$（$w_i$為$u->v$的邊權(quán)）

?

1 //It is made by Awson on 2017.9.21 2 #include <set> 3 #include <map> 4 #include <cmath> 5 #include <ctime> 6 #include <queue> 7 #include <stack> 8 #include <string> 9 #include <cstdio> 10 #include <vector> 11 #include <cstdlib> 12 #include <cstring> 13 #include <iostream> 14 #include <algorithm> 15 #define Min(a, b) ((a) < (b) ? (a) : (b)) 16 #define Max(a, b) ((a) > (b) ? (a) : (b)) 17 #define LL long long 18 using namespace std; 19 const int N = 50000; 20 const int M = 100000; 21 LL st[64]; 22 23 int n, m, u, v; 24 LL c; 25 struct tt { 26 int to, next; 27 LL cost; 28 }edge[2*M+5]; 29 int path[N+5], top; 30 LL d[N+5]; 31 LL p[64]; 32 bool vis[N+5]; 33 34 LL getmax(LL x) { 35 for (int i = 62; i >= 0; i--) 36 if ((x^p[i]) > x) 37 x ^= p[i]; 38 return x; 39 } 40 void insert(LL x) { 41 for (int i = 62; i >= 0; i--) 42 if (x&st[i]) { 43 if (!p[i]) { 44 p[i] = x; 45 break; 46 } 47 x ^= p[i]; 48 } 49 } 50 void add(int u, int v, LL c) { 51 edge[++top].to = v; 52 edge[top].cost = c; 53 edge[top].next = path[u]; 54 path[u] = top; 55 } 56 void dfs(int u) { 57 vis[u] = 1; 58 for (int i = path[u]; i; i = edge[i].next) { 59 if (vis[edge[i].to]) insert(d[u]^d[edge[i].to]^edge[i].cost); 60 else { 61 d[edge[i].to] = d[u]^edge[i].cost; 62 dfs(edge[i].to); 63 } 64 } 65 } 66 void work() { 67 st[0] = 1; 68 for (int i = 1; i < 63; i++) st[i] = st[i-1]<<1; 69 for (int i = 1; i <= m; i++) { 70 scanf("%d%d%lld", &u, &v, &c); 71 add(u, v, c); add(v, u, c); 72 } 73 dfs(1); 74 LL ans = getmax(d[n]); 75 printf("%lld\n", ans); 76 } 77 int main() { 78 while (~scanf("%d%d", &n, &m)) 79 work(); 80 return 0; 81 }

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/NaVi-Awson/p/7568739.html

總結(jié)

以上是生活随笔為你收集整理的[WC 2011]Xor的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。