【題目描述】
BZOJ2115XOR——線性基

【題目分析】
這道題看完以后很懵逼，人家要是走的很復(fù)雜呢？各種繞來繞去怎么辦？
首先我們應(yīng)該注意到一個(gè)很明顯的道理：重復(fù)的路徑會(huì)和自身抵消，所以我們大可以隨便跑，只要再跑回來就對(duì)答案沒有影響。因此，有影響的只有選擇的路徑和經(jīng)過的環(huán)，因?yàn)榄h(huán)是可以回到已經(jīng)經(jīng)過的點(diǎn)而不抵消的。而且只要我們?cè)敢馕覀兛梢匀ト魏我粋€(gè)環(huán)（假如環(huán)有一個(gè)起點(diǎn)x，我們有一條從1到n的路徑，可能這個(gè)環(huán)和路徑?jīng)]有交點(diǎn)，但是我們可以從某一點(diǎn)跑到x然后經(jīng)過這個(gè)環(huán)再跑回來，這樣我們就經(jīng)過這個(gè)環(huán)了）
我們算法的策略是：任選一個(gè)從1到n路徑的xor和作為初始值然后再以各個(gè)環(huán)作為線性基求最大值
可能你會(huì)疑惑，任意選一個(gè)路徑真的沒有問題嗎？假如從1到n只有這一條路徑我們顯然必須選，可是有很多路徑的時(shí)候他們就會(huì)構(gòu)成環(huán)，而我們已經(jīng)將各種環(huán)都加入線性基了，通過選的這條路和其他環(huán)的異或我們就能得到其他路徑（相當(dāng)于可以被抵消）
另外，面向板子編程真的好爽，以后一定要認(rèn)認(rèn)真真的整理板子。這個(gè)線性基的板子就挺好用
【參考博客】
BZOJ2115 [Wc2011] Xor
【AC代碼】

#include<cstdio> #include<cstring> #include<cmath> #include<climits> #include<cstdlib> #include<algorithm> #include<queue> #include<vector> #include<set>using namespace std;typedef long long ll;const int MAXN=50005; const int MAXM=100005; struct node {int from,to;ll weight; }edge[MAXM<<1]; int head[MAXM<<1],nxt[MAXM<<1]; int tot=0; int n,m; ll dis[MAXN]; bool vis[MAXN];struct L_B {ll b[65],p[65];int cnt,flag;L_B(){memset(p,0,sizeof(p));memset(b,0,sizeof(b));cnt=flag=0;}inline bool insert(ll x){for(int i=62;i>=0;--i)if(x&(1ll<<i)){if(b[i])x^=b[i];else{b[i]=x;return true;}}flag=1;return false;}ll get_max(){ll ret = 0;for(int i=62;i>=0;--i)if((ret^b[i])>ret)ret^=b[i];return ret;}ll get_max(ll initval){ll ret = initval;for(int i=62;i>=0;--i)if((ret^b[i])>ret)ret^=b[i];return ret;}ll get_min(){if(flag)return 0;for(int i=0;i<=62;++i)if(b[i])return b[i];return 0;}inline void rebuild(){for(int i = 1;i <= 62;++i)if(b[i])for(int j=0;j<i;++j)if(b[i]&(1ll<<j))b[i]^=b[j];for(int i=0;i<=62;++i)if(b[i])p[cnt++]=b[i];}ll kth(ll k){if(flag)--k;if(k==0)return 0;ll ret = 0;if(k>=(1ll<<cnt))return -1;for(int i=0;i<=cnt-1;++i)if(k&(1ll<<i))ret^=p[i];return ret;} }; L_B lis;inline int getint(){int w=0,q=0;char c=getchar();while((c<'0'||c>'9')&&c!='-')c=getchar();if(c=='-')q=1,c=getchar();while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w;} inline ll getlong(){ll w=0,q=0;char c=getchar();while((c<'0' || c>'9')&&c!='-')c=getchar();if(c=='-') q=1,c=getchar();while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w;}void AddEdge(int u,int v,ll w) {tot++;edge[tot].from=u; edge[tot].to=v; edge[tot].weight=w;nxt[tot]=head[u]; head[u]=tot; }void dfs(int x) {int v;vis[x]=true;for(int i=head[x];i;i=nxt[i]){v=edge[i].to;if(!vis[v]){dis[v]=dis[x]^edge[i].weight;dfs(v);}else{lis.insert(dis[x]^dis[v]^edge[i].weight);}} }int main() {int u,v; ll w;n=getint(); m=getint();for(int i=0;i<m;i++){u=getint(); v=getint(); w=getlong(); AddEdge(u,v,w); AddEdge(v,u,w);}dfs(1);printf("%lld",lis.get_max(dis[n]));return 0; }

總結(jié)

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

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