BZOJ 2115: [Wc2011] Xor DFS + 线性基

2115: [Wc2011] Xor

Time Limit: 10 Sec Memory Limit: 259 MB

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

HINT

Source

题解：

　　整个1->n的过程就是一堆环和一条简单路径的异或和

　　任意环的异或和任意组合起来，这个可以高斯消元求解，偷个懒利用线性基也是可以的

　　15年ccpc南阳与这个题做法相同，，算是双倍经验题：传送门

#include<bits/stdc++.h>
using namespace std;
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
typedef unsigned long long ULL;
const long long INF = 1e18+1LL;
const double pi = acos(-1.0);
const int N=5e5+20,M=1e6+10,inf=2147483647;


LL dep[N],a[N],ins[N],ans;
int n,m,vis[N],cnt,t = 2,head[N],has[N];
struct ss {
    int to,next,id;
    LL c;
}e[N * 2];
void add(int u,int v,LL w,int id) {
    e[t].next = head[u];
    e[t].to = v;
    e[t].c = w;
    e[t].id = id;
    head[u] = t++;
}
void dfs(int u,int f) {
    vis[u] = vis[f] + 1;
    for(int i = head[u]; i; i = e[i].next) {
        int to = e[i].to;
        if(has[e[i].id] || (vis[to] && vis[to] < vis[u])) continue;
        if(vis[to]) {
            a[++cnt] = dep[to] ^ dep[u] ^ e[i].c;
            continue;
        }
        has[e[i].id] = 1;
        dep[to] = dep[u] ^ e[i].c;
        dfs(to,u);
    }
}
void go(int u,LL now) {
    if(u == n) {
        LL ret = now;
         for(int i = 62; i >= 0; --i)
              if((ins[i]^ret) > ret) ret^=ins[i];
        ans = max(ans,ret);
        return ;
    }
    vis[u] = 1;
    for(int i = head[u]; i; i = e[i].next) {
        int to = e[i].to;
        if(has[e[i].id]) continue;
        has[e[i].id] = 1;
        go(to,now^e[i].c);
    }
    vis[u] = 0;
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; ++i) {
        int x,y;LL z;
        scanf("%d%d%lld",&x,&y,&z);
        if(x == y) {
            a[++cnt] = z;
            continue;
        }
        add(x,y,z,i),add(y,x,z,i);
    }
    dfs(1,0);
    for(int i = 1; i <= cnt; ++i) {
        for(int j = 62; j >= 0; --j) {
            if(a[i]&(1LL<<j)) {
                if(!ins[j]) {
                    ins[j] = a[i];
                    break;
                }
                a[i] ^= ins[j];
            }
        }
    }
    ans = 0;
    memset(vis,0,sizeof(vis));
    memset(has,0,sizeof(has));
    go(1,0);
    cout<<ans<<endl;
    return 0;
}