bzoj 2115: [Wc2011] Xor xor高斯消元

2115: [Wc2011] Xor

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 797  Solved: 375
[Submit][Status]

Description

bzoj 2115: [Wc2011] Xor xor高斯消元

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

6

HINT

bzoj 2115: [Wc2011] Xor xor高斯消元

Source

  本题对于我来说难点在于如何枚举出所有的环,想了半天tarjan,结果发现只需要dfs一次就行了,仔细想一下,也没什么反例。

  剩下就是xor高斯消元了,注意去重。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
#define MAXN 51000
#define MAXV 51000
#define MAXL 1000000
#define MAXE MAXV*4
typedef long long qword;
struct Edge
{
int np;
qword val;
Edge *next;
}E[MAXE],*V[MAXV];
int tope=-;
void addedge(int x,int y,qword z)
{
E[++tope].np=y;
E[tope].val=z;
E[tope].next=V[x];
V[x]=&E[tope];
}
bool vis[MAXN];
qword path_val[MAXN];
qword vec[MAXL];
int totv=;
set<qword> S;
void dfs(int now,qword pv)
{
Edge *ne;
path_val[now]=pv;
vis[now]=true;
for (ne=V[now];ne;ne=ne->next)
{
if (vis[ne->np])
{
if (S.find(path_val[ne->np] ^ path_val[now] ^ ne->val)==S.end())
{
vec[totv++]=path_val[ne->np] ^ path_val[now] ^ ne->val;
S.insert(vec[totv-]);
}
}else
{
dfs(ne->np,pv^(ne->val));
}
}
}
bool cmp_v(qword x,qword y)
{
return x>y;
}
int main()
{
freopen("input.txt","r",stdin);
int n,m;
scanf("%d%d",&n,&m);
int i,j,k,x,y;
qword z;
for (i=;i<m;i++)
{
scanf("%d%d%lld",&x,&y,&z);
addedge(x,y,z);
addedge(y,x,z);
}
dfs(,);
for (i=;i<totv;i++)
{
sort(vec+i,vec+totv,cmp_v);
totv=unique(vec+i,vec+totv)-vec;
for (j=i+;j<totv;j++)
if ((vec[j]^vec[i])<vec[j])
vec[j]^=vec[i];
}
z=path_val[n];
for (i=;i<totv;i++)
if ((z^vec[i])>z)
z^=vec[i];
printf("%lld\n",z);
}
上一篇:BZOJ 2337 XOR和路径 | 高斯消元 期望 位运算


下一篇:030、Java中的求模计算