BZOJ2115 Xor

題目描述：

?

題目大意：

給定一張 n 個點 m 條邊的無向帶權連通圖，求一條從點 1 到點 n 的路徑，使得經過的邊權異或和最大。

路徑可以經過重復點和重復邊，當一條邊被重復經過時也會相應地被 xor 多次。

solution

顯然（然而我不會嚴格證明QAQ），答案是由一條 1 到 n 的路徑和若干基本環構成的。

先做一個??序，此處定義所有由??中兒子連向父親的邊稱為返祖邊。

則每一條返祖邊會產生一個基本環。

先選擇一條1->n的路徑，再從所有基本環里選擇若干湊出最大異或和即可。

顯然可以用線性基維護所有基本環的值。

So easy！

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=200005; struct enode{int to; ll c;}; bool vis[MAXN]; int num=0,n,m; ll s[MAXN],g[MAXN]; vector<enode> e[MAXN]; ll read() {ll f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+c-'0'; c=getchar(); }return x*f; } void dfs(int x,int father) {//cout<<x<<" "<<s[x]<<endl;vis[x]=1;for (int i=0;i<e[x].size();i++)if (!vis[e[x][i].to]) {s[e[x][i].to]=s[x]^e[x][i].c;dfs(e[x][i].to,x);}else if (e[x][i].to!=father) g[++num]=s[x]^s[e[x][i].to]^e[x][i].c; } struct Xor_Basis {int maxsz;ll basis[65];void init(){ memset(basis,0,sizeof basis); maxsz=63; }bool insert(ll x){for (int i=maxsz;i>=0;i--) if ((x>>i)&1)if (basis[i]) x^=basis[i];else { basis[i]=x; break; }return x; } } QAQ; int main() {QAQ.init();n=read(),m=read();for (int i=1;i<=m;i++){int u=read(),v=read();ll c=read();e[u].push_back((enode){v,c});e[v].push_back((enode){u,c});}dfs(1,0);for (int i=1;i<=num;i++) QAQ.insert(g[i]);ll ans=s[n];for (int i=QAQ.maxsz;i>=0;i--) if (!((ans>>i)&1)) ans^=QAQ.basis[i];printf("%lld\n",ans);return 0; }

代碼較丑，不喜勿噴。

總結

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

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