Ba Gua Zhen
Time Limit: 6000/4000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 304 Accepted Submission(s): 93
Fortunately, there was an old man named Chengyan Huang who was willing to help Xun Lu to hack the puzzle. Chengyan told Xun Lu that he had to choose a vertex as the start point, then walk through some of the edges and return to the start point at last. During his walk, he could go through some edges any times. Since Liang Zhuge had some mysterious magic, Xun Lu could hack the puzzle if and only if he could find such a path with the maximum XOR sum of all the edges length he has passed. If the he passed some edge multiple times, the length would also be calculated by multiple times. Now, could you tell Xun Lu which is the maximum XORcircuit path in this puzzle to help him hack the puzzle?
Each test case begins with two integers N(2≤N≤5×104) and M(1≤M≤105) in one line. Then M lines follow. Each line contains three integers ui, viand wi(1≤ui,vi≤N,0≤wi≤260−1) to describe all the edges in the puzzle.
3 3
1 2 1
1 3 2
2 3 0
6 7
1 2 1
1 3 1
2 3 1
3 4 4
4 5 2
4 6 2
5 6 2
Case #2: 3
A XOR takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits.
The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1.
In this we perform the comparison of two bits, being 1 if the two bits are different, and 0 if they are the same.
分析:可以拆成几个简单环来做,这样做就不会有问题。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<functional>
#include <cassert>
using namespace std;
typedef long long LL; const int maxn = ;
const int maxm = ;
struct node {
int nex;
}a[maxn];
struct edge {
int nex, y;
LL v;
}e[maxm];
int p;
long long stack[maxn];
int top;
int tot;
int f[maxn];
long long num[];
void add(int X, int Y, LL V) {
p++;
e[p].nex = a[X].nex;
e[p].v = V;
a[X].nex = p;
e[p].y = Y;
}
bool vis[maxn];
void dfs(int x) {
f[x] = ++top;
vis[x] = true;
for (int t = a[x].nex; t; t = e[t].nex) {
int y = e[t].y; if (f[y] == ) {
stack[y] = stack[x] ^ e[t].v;
dfs(y);
}else {
if (!vis[y]) continue;
num[++tot] = stack[x] ^ e[t].v ^ stack[y];
//cout << x << " " << num[tot] << " " << s << " " << y << endl;
}
}
vis[x] = false;
} LL b[], bN;
void solve() {
bN = ;
// swap(num[3], num[2]);
for (int i = ; i <= tot; ++ i) {
// printf("%lld\n", num[i]);
for (int j = ; j < bN; ++ j) {
if ((num[i]^b[j]) < num[i])
num[i] = num[i] ^ b[j];
}
if (num[i])
b[bN ++] = num[i];
} sort(b, b+bN, greater<LL>());
// for (int i = 0; i < bN; ++ i) printf("%lld ", b[i]); LL res = ;
for (int i = ; i < bN; ++ i)
if ((res ^ b[i]) > res)
res ^= b[i];
printf("%I64d\n", res);
// printf("%lld\n", res);
} int T, cas = , n, m;
int main() {
// freopen("e.in","r",stdin);
scanf("%d", &T);
while (T--) {
printf("Case #%d: ", ++cas);
scanf("%d%d", &n, &m);
p = ;
memset(a,,sizeof(a));
memset(e,,sizeof(e));
for (int i = ; i <= m; i++) {
int x, y; LL v;
scanf("%d%d", &x, &y);
// scanf("%lld", &v);
scanf("%I64d", &v);
add(x, y, v);
add(y, x, v);
}
memset(stack,,sizeof(stack));
top = ;
tot = ;
memset(vis,,sizeof(vis));
memset(f,,sizeof(f));
dfs();
//for (int i = 1; i <= tot; i++) cout << num[i] << endl;
sort(num+, num++tot); tot = unique(num+, num++tot) - (num+);
// for (int i = 1; i <= tot; i++) cout << num[i] << endl;
solve();
}
return ;
}