BZOJ 2115 Xor(线性基)

2022-08-14 08:57:13

题意：给定一个n<=50000个点m<=100000条边的无向联通图，每条边上有一个权值wi<=1e18。请你求一条从1到n的路径，使得路径上的边的异或和最大.

任意一条1到n的路径的异或和，都可以由任意一条1到n路径的异或和与图中的一些环的异或和来组合得到。

为什么？假如我们已经有一条1到n的路径，考虑在出发之前，先走到图中任意一个环上面，走一遍这个环，然后原路返回，这样我们既得到了这个环的异或值（走到环的路径被走过了 2 次，抵消了），也返回了点1。我们可以对任意的环这样做，从而获得这个环的异或值。有了这个性质，不难验证上述结论是正确的。

现在的解题思路就非常明确了，首先找出所有的环（利用 DFS 树中的返祖边来找环），然后找一条任意的1到n的路径，其异或值为ans。则我们就需要选择若干个环，使得这些这些环上的异或值与ans异或起来最大。这就转化为线性基的问题了。

求出所有环的异或值的线性基，由于线性基的良好性质，只需要从大到小考虑选择每个线性基向量能否使得异或值更大即可，容易用贪心证明正确性。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

struct Edge{int p, next; LL w;}edge[N<<];

int head[N], cnt=, vis[N], num;

LL p[], node[N], a[N*];

void add_edge(int u, int v, LL w)

{

    edge[cnt].p=v; edge[cnt].next=head[u]; edge[cnt].w=w; head[u]=cnt++;

}

void dfs(int x, int fa)

{

    vis[x]=;

    for (int i=head[x]; i; i=edge[i].next) {

        int v=edge[i].p;

        if (v==fa) continue;

        if (vis[v]) a[++num]=node[v]^node[x]^edge[i].w;

        else node[v]=node[x]^edge[i].w, dfs(v,x);

    }

}

void sol()

{

    FOR(i,,num) {

        for (int j=; j>=; --j) {

            if (!(a[i]>>j)) continue;

            if (!p[j]){p[j]=a[i]; break;}

            a[i]^=p[j];

        }

    }

}

int main ()

{

    int n, m, u, v;

    LL w;

    scanf("%d%d",&n,&m);

    while (m--) scanf("%d%d%lld",&u,&v,&w), add_edge(u,v,w), add_edge(v,u,w);

    dfs(,);

    sol();

    LL ans=node[n];

    for (int i=; i>=; --i) if ((ans^p[i])>ans) ans^=p[i];

    printf("%lld\n",ans);

    return ;

}
上一篇：[BZOJ 2115] Xor


下一篇：bzoj 2115 Xor - 线性基 - 贪心