BZOJ 2115: [Wc2011] Xor

2115: [Wc2011] Xor

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 2884 Solved: 1225
[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

Source

[Submit][Status][Discuss]

本来挺水的一道题，因为一个细节上的long long问题，WA了一晚上。

明天还有WC呢，要睡觉了，/(ㄒoㄒ)/~~

这题乍一看和线性基不沾边哈，但确实是线性基，2333~~~

一个发现——所有路径均可以分为一条从1到n的简单路径+若干个简单环。

所以从原图中随意找一棵生成树，在树上跑DFS求出每个点到根的路径和（异或意义上的）。

然后找出所有的基本环（只包含一条非树边），其环上的异或和为Dis[x]^Dis[y]^Val[i]。

所有的简单环都可以由基本环组成，所以我们就有了所有环——子集异或和。

那么，这不就是线性基的问题吗？求出线性基之后贪心“增广”1到n的路径即可。

 1 #include <bits/stdc++.h>
 2 
 3 typedef long long lnt;
 4 
 5 const int mxn = 500005;
 6 
 7 int n, m;
 8 
 9 int hd[mxn];
10 int to[mxn];
11 int nt[mxn];
12 lnt vl[mxn];
13 
14 inline void addEdge(int u, int v, lnt w)
15 {
16     static int tot = 0;
17     
18     nt[tot] = hd[u];
19     to[tot] = v;
20     vl[tot] = w;
21     hd[u] = tot++;
22 }
23 
24 int vis[mxn];
25 lnt dis[mxn];
26 lnt cir[mxn];
27 int tot;
28 
29 void dfs(int u)
30 {
31     vis[u] = true;
32     
33     for (int i = hd[u], v; ~i; i = nt[i])
34         if (!vis[v = to[i]])
35             dis[v] = dis[u] ^ vl[i], dfs(v);
36         else
37             cir[++tot] = dis[u] ^ dis[v] ^ vl[i];
38 }
39 
40 int cnt;
41 
42 inline void gauss(void)
43 {
44     for (int i = 1; i <= tot; ++i)
45     {
46         for (int j = tot; j > i; --j)
47             if (cir[i] < cir[j])
48                 std::swap(cir[i], cir[j]);
49         
50         if (cir[i])
51             ++cnt;
52         else
53             break;
54         
55         for (int j = 63; ~j; --j)
56             if ((cir[i] >> j) & 1)
57             {
58                 for (int k = 1; k <= tot; ++k)
59                     if (i != k && (cir[k] >> j) & 1)
60                         cir[k] ^= cir[i];
61                 
62                 break;
63             }
64     }
65 }
66 
67 inline void solve(void)
68 {
69     lnt ans = dis[n];
70     
71     for (int i = 1; i <= cnt; ++i)
72         ans = std::max(ans, ans ^ cir[i]);
73     
74     printf("%lld
", ans);
75 }
76 
77 signed main(void)
78 {
79     scanf("%d%d", &n, &m);
80     
81     memset(hd, -1, sizeof(hd));
82     
83     for (int i = 1; i <= m; ++i)
84     {
85         static int x, y;
86         static lnt w;
87         
88         scanf("%d%d%lld", &x, &y, &w);
89         
90         addEdge(x, y, w);
91         addEdge(y, x, w);
92     }
93     
94     dfs(1);
95     
96     gauss();
97     
98     solve();
99 }

@Author: YouSiki