BZOJ 2115: [Wc2011] Xor

2115: [Wc2011] Xor

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

分析：

我们YY一下就可以发现这条最优路径是由一条从$1$到$n$的简单路径+一堆简单环构成的，所以我们先搞一颗最小生成树，然后往其中加入边$(x,y)$，并且计算加入$(x,y)$之后的简单环的权值，这些环的权值就是可选值，然后随便选取一条从$1$到$n$的路径，这是必选值，这样我们就可以求出可选值的线性基然后根据最高位的$1$是唯一的性质贪心求出最大路径权值...

代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std;

const int maxn=50000+5,maxm=100000+5;

struct M{
	
	int x,y;
	long long v;
	
	friend bool operator < (M a,M b){
		return a.v<b.v;
	}
	
}e[maxm];

int n,m,cnt,tot,fa[maxn],hd[maxn],to[maxm<<1],nxt[maxm<<1],vis[maxm];

long long ans,w[maxm<<1],dis[maxn],val[maxm];

inline int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}

inline void add(long long s,int x,int y){
	w[cnt]=s;to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++;
}

inline void kruskal(void){
	sort(e+1,e+m+1);
	for(int i=1;i<=m;i++){
		int fx=find(e[i].x),fy=find(e[i].y);
		if(fx!=fy)
			add(e[i].v,e[i].x,e[i].y),add(e[i].v,e[i].y,e[i].x),fa[fx]=fy,vis[i]=1;
	}
}

inline void dfs(int root,int f){
	for(int i=hd[root];i!=-1;i=nxt[i])
		if(to[i]!=f)
			dis[to[i]]=dis[root]^w[i],dfs(to[i],root);
}

inline void xor_gauss(void){
	tot=cnt,cnt=0;
	for(int i=1;i<=tot;i++){
		for(int j=tot;j>i;j--)
			if(val[j]>val[i])
				swap(val[i],val[j]);
		if(val[i])
			cnt++;
		else
			break;
		for(int j=63;j>=0;j--)
			if((val[i]>>j)&1){
				for(int k=1;k<=tot;k++)
					if(k!=i&&((val[k]>>j)&1))
						val[k]^=val[i];
				break;
			}
	}
}

signed main(void){
	scanf("%d%d",&n,&m);
	memset(hd,-1,sizeof(hd));
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
		scanf("%d%d%lld",&e[i].x,&e[i].y,&e[i].v);
	kruskal();dfs(1,-1);cnt=0;
	for(int i=1;i<=m;i++)
		if(!vis[i])
			val[++cnt]=dis[e[i].x]^dis[e[i].y]^e[i].v;
	xor_gauss();ans=dis[n];
	for(int i=1;i<=cnt;i++)
		ans=max(ans,ans^val[i]);
	printf("%lld
",ans);
	return 0;
}

By NeighThorn