BZOJ 2115 Xor（线性基+图论）

最新推荐文章于 2019-12-19 18:24:14 发布

alpc_qleonardo

最新推荐文章于 2019-12-19 18:24:14 发布

阅读量340

点赞数

分类专栏： ----------------图论------------- ---------Online Judge-------- BZOJ 线性基 --------------数学------------- 文章标签： BZOJ 线性基图论

本文链接：https://blog.csdn.net/u013534123/article/details/79902505

版权

---------Online Judge-------- 同时被 3 个专栏收录

329 篇文章

订阅专栏

--------------数学-------------

131 篇文章

订阅专栏

----------------图论-------------

46 篇文章

订阅专栏

2115: [Wc2011] Xor

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 4636 Solved: 1939
[ Submit][ Status][ Discuss]

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

大致题意：给你一个图，然后可以随便走，问你从1到n的所有走法中，异或和最大是多少。

方法也很简单，首先随便找一条1到n的路径，求出其异或和作为初始值，然后把图中的所有环的异或和求出来，把这些环的异或和加入线性基中，求最大的异或和即可。

说起来简单，下面开始证明方法的正确性。首先是为什么只是选取环的异或和，如果这个环与我初始选择的路径不相交怎么办。其实呢，根据异或的性质，如果选择的路与环不想交，我完全可以先按照一种方式走到环，在里面转了一圈之后，再原路返回到初始选择的路径，这样从初始路径到环的路走了两次，异或抵消。所以说，环可以任意选取。

其次，为什么是任意选择一条初始路径。我们可以这么考虑，如果选择另一条从1到n的路径比我们最初选择的路径更优，那么这条路径首先肯定与我们初始选择的路径构成一个环。既然构成一个环，那么就会在选取最大异或和的过程中考虑。如果选择这个环，那么会异或这个环内的异或和，我们初始选择的路径就会被异或两次抵消，相当于初始路径就是另一个更优的。

dfs求出所有环的异或和，并且顺便求一条1到n的路径的异或和。最后，就是一个线性基的经典问题了。具体见代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>
#define LL long long
#define N 500010
using namespace std;

struct Linear_Basis
{
    LL b[63],nb[63],tot;

    void init()
    {
        tot=0;
        memset(b,0,sizeof(b));
        memset(nb,0,sizeof(nb));
    }

    bool ins(LL x)
    {
        for(int i=62;i>=0;i--)
            if (x&(1LL<<i))
            {
                if (!b[i]) {b[i]=x;break;}
                x^=b[i];
            }
        return x>0;
    }

    LL Max(LL x)
    {
        LL res=x;
        for(int i=62;i>=0;i--)
            res=max(res,res^b[i]);
        return res;
    }

    LL Min(LL x)
    {
        LL res=x;
        for(int i=0;i<=62;i++)
            if (b[i]) res^=b[i];
        return res;
    }

    void rebuild()
    {
        for(int i=62;i>=0;i--)
            for(int j=i-1;j>=0;j--)
                if (b[i]&(1LL<<j)) b[i]^=b[j];
        for(int i=0;i<=62;i++)
            if (b[i]) nb[tot++]=b[i];
    }

    LL Kth_Max(LL k)
    {
        LL res=0;
        for(int i=62;i>=0;i--)
            if (k&(1LL<<i)) res^=nb[i];
        return res;
    }

} LB;

struct Edge{int y;LL w;};
LL s[N],w[N],loop[N];
vector<Edge> g[N];
int n,m,tot;
bool v[N];

void dfs(int x)
{
    v[x]=1;
    for(int i=0;i<g[x].size();i++)
    {
        int y=g[x][i].y;
        LL w=g[x][i].w;
        if (!v[y]) s[y]=s[x]^w,dfs(y);
         else loop[++tot]=s[y]^s[x]^w;
    }
}

int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		LB.init();
		for(int i=1;i<=m;i++)
        {
            int u,v; LL p;
            scanf("%d%d%lld",&u,&v,&p);
            g[u].push_back(Edge{v,p});
            g[v].push_back(Edge{u,p});
        }
        tot=0; dfs(1);
        for(int i=1;i<=tot;i++)
            LB.ins(loop[i]);
        printf("%lld\n",LB.Max(s[n]));
	}
}