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

Solution

首先這個答案肯定是由一條簡單路徑和幾個環構成的。簡單路徑外的環，我們是可以想用就用的，因為我們可以走到環那里繞一圈再回到起點，這樣除了那個環之外別的地方都沒有受到影響。

怎么求出所有的環呢？其實就是$DFS$樹所有的反祖邊和樹邊構成的環，$DFS$一下就可以找出來了。

我們找出所有的環，再隨便找一條$1$到$n$的簡單路徑，用簡單路徑的$xor$去在環的線性基里找最大就好了。

為什么隨便找一條簡單路徑是對的呢？因為我們找出的所有環中，肯定有在簡單路徑上的，這樣的話簡單路徑在異或上這些環后，就會變成一條新的簡單路徑，這樣調整下來最后肯定能得到最優解。

Code

1 #include<iostream> 2 #include<cstdio> 3 #define N (200009) 4 #define LL long long 5 using namespace std; 6 7 struct Edge{LL to,next,len;}edge[N<<1]; 8 LL n,m,u,v,l,cnt; 9 LL head[N],num_edge; 10 LL d[N],Xor[N],Circle[N]; 11 bool vis[N]; 12 13 void add(LL u,LL v,LL l) 14 { 15 edge[++num_edge].to=v; 16 edge[num_edge].len=l; 17 edge[num_edge].next=head[u]; 18 head[u]=num_edge; 19 } 20 21 void Insert(LL x) 22 { 23 for (int i=62; i>=0; --i) 24 if (x&(1ll<<i)) 25 { 26 if (!d[i]) {d[i]=x; break;} 27 x^=d[i]; 28 } 29 } 30 31 void DFS(LL x) 32 { 33 vis[x]=1; 34 for (int i=head[x]; i; i=edge[i].next) 35 { 36 int y=edge[i].to; 37 if (!vis[y]) Xor[y]=Xor[x]^edge[i].len, DFS(y); 38 else Circle[++cnt]=Xor[y]^Xor[x]^edge[i].len; 39 } 40 } 41 42 int main() 43 { 44 scanf("%lld%lld",&n,&m); 45 for (int i=1; i<=m; ++i) 46 { 47 scanf("%lld%lld%lld",&u,&v,&l); 48 add(u,v,l); add(v,u,l); 49 } 50 DFS(1); 51 for (int i=1; i<=cnt; ++i) 52 Insert(Circle[i]); 53 LL ans=Xor[n]; 54 for (int i=62; i>=0; --i) 55 ans=max(ans,ans^d[i]); 56 printf("%lld\n",ans); 57 }

轉載于:https://www.cnblogs.com/refun/p/10277334.html

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的BZOJ2115:[WC2011] Xor(线性基)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。