【題目分析】

? ? 顯然，一個路徑走過兩邊是不需要計算的，所以我么找到一條1-n的路徑，然后向該異或值不斷異或簡單環即可。

? ? 但是找出所有簡單環是相當復雜的，我們只需要dfs一遍，找出所有的環路即可，因為所有的簡單環都可以經過各種各樣的異或得到。

? ? 然后線性基，在從高位向低位貪心即可，至于證明，需要擬陣的相關知識。

【代碼】

#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath>#include <set> #include <map> #include <string> #include <algorithm> #include <vector> #include <iostream> #include <queue> using namespace std;#define maxn 100005 #define ll long longint read() {int x=0,f=1; char ch=getchar();while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}return x*f; }int h[maxn],to[maxn<<1],ne[maxn<<1]; ll w[maxn<<1]; int en=0,n,m,vis[maxn],tot=0; ll a[maxn<<1]; ll dis[maxn];void add(int a,int b,ll c) {to[en]=b;w[en]=c;ne[en]=h[a];h[a]=en++; }void dfs(int k) { // printf("dfs on %d\n",k);vis[k]=1;for (int i=h[k];i>=0;i=ne[i]){if (!vis[to[i]]){dis[to[i]]=dis[k]^w[i];dfs(to[i]);}else a[++tot]=dis[k]^dis[to[i]]^w[i];} }ll lb[64],ans;int main() {memset(h,-1,sizeof h);scanf("%d%d",&n,&m);for (int i=1;i<=m;++i){int a,b; ll c;scanf("%d%d%lld",&a,&b,&c);add(a,b,c);add(b,a,c);}dfs(1);ans=dis[n]; // for (int i=1;i<=n;++i) cout<<dis[i]<<" "; cout<<endl; // for (int i=1;i<=tot;++i) cout<<a[i]<<" ";cout<<endl;for (int i=1;i<=tot;++i){for (int j=63;j>=0;j--){if ((a[i]>>j)&1){if (!lb[j]) {lb[j]=a[i];break;}else a[i]^=lb[j];}}}for (int i=63;i>=0;i--)if (lb[i]&&((ans>>i)&1)==0) ans^=lb[i];cout<<ans<<endl;return 0; }

　　

轉載于:https://www.cnblogs.com/SfailSth/p/6204776.html

總結

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

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