CC

自然万物都趋向从有序变得无序

0%

BZOJ 2115 Xor(线性基 + dfs)

发表于 更新于 分类于 Valine：

题目链接

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Input

第一行包含两个整数N和 M， 表示该无向图中点的数目与边的数目。 接下来M 行描述 M 条边，每行三个整数Si，Ti ，Di，表示 Si 与Ti之间存在 一条权值为 Di的无向边。 图中可能有重边或自环。

Output

仅包含一个整数，表示最大的XOR和（十进制结果）,注意输出后加换行回车。

Sample intput

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

6

样例解释

题意:

一张无向图，从节点1走到节点n，所有点和边都可以重复走，将走过的路径上的每条边的权值异或，求异或最大值。一条边走多次则异或多次。

思路:

由于可以无限制的走，而且同一数被异或两次等于没有异或，那么我们可以知道之后的路径应该是一条线加上一些环，因为其他的重复走偶数次的边抵消了。

那么对于答案，我们应该先找到一条1到n的路径，然后为了使得权值最大，我们要加一些环去进去，至于加哪些环呢，我们可以对所有的环求一次线性基，利用线性基的性质可以很好的求出我们能得到的最大的答案了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*************************************************************************
    > File Name: bzoj-2115.cpp
    > Author: wood
    > Mail: cbcruel@gmail.com
    > Created Time: 2018年08月07日 星期二 15时33分30秒
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<string>

using namespace std;
typedef long long LL;
#define sqr(x) (x)*(x)
const double eps = 1e-8;
const double C = 0.57721566490153286060651209;
const double pi = acos(-1.0);
const LL mod = 1e9 + 7;
const int maxn = 5e4 + 10;
const int MAX_BASE = 62;
#define mp make_pair

vector<pair<int, LL> > w[maxn];
LL a[maxn*100], b[MAX_BASE+10];
LL dis[maxn];
bool vis[maxn];
int cnt;

void solve(int n) {
    memset(b, 0, sizeof b);
    for (int i = 0; i < n; ++i)
        for (int j = MAX_BASE; j >= 0; --j)
            if (a[i] >> j & 1) {
                if (b[j]) a[i] ^= b[j];
                else {
                    b[j] = a[i];
                    for (int k = j - 1; k >= 0; --k)
                        if (b[k] && (b[j] >> k & 1))
                            b[j] ^= b[k];
                    for (int k = j + 1; k <= MAX_BASE; ++k)
                        if (b[k] >> j & 1)
                            b[k] ^= b[j];
                    break;
                }
            }
}

void dfs(int u){
    vis[u] = 1;
    for(int i = 0; i < w[u].size(); ++i){
        pair<int, LL> x = w[u][i];
        if(!vis[x.first]){
            dis[x.first] = dis[u] ^ x.second;
            dfs(x.first);
        }else a[cnt++] = dis[u] ^ dis[x.first] ^ x.second;
    }
}

int main(){
    int n, m;
    ios::sync_with_stdio(0);
    cin >> n >> m;
    while(m--){
        int x, y;
        LL d;
        cin >> x >> y >> d;
        w[x].push_back(mp(y,d));
        w[y].push_back(mp(x,d));
    }cnt = 0;
    dfs(1);solve(cnt);
    LL ans = dis[n];
    for(int i = 0; i <= MAX_BASE; ++i)
        if(ans <(ans^b[i])) ans ^= b[i];
    cout << ans << endl;
    return 0;
}