注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 2115 xor  

2014-01-16 08:17:43|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
DFS出一棵树之后,容易异或之后还可能留着的东西只有两种:
DFS树上1~n的路径异或和
任何一个环的异或和
第一个是定值……第二个是要求的
问题转化为求n个数中选若干个数与定值异或和最大的值
经典问题
可是……我不会?!

于是怒去看sgu 275的题解
大概思路就是……我们要通过枚举常数让列出来的方程有解
所以只要没有自由元即可

其实相信大家应该不会傻到像我一样不知道怎么做把

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<bitset>
#define maxn 50010
#define maxm 400010
using namespace std;
typedef long long LL;
template<class T>
void Read(T &digit)
{
digit=0;
char c;
for(c=getchar();!isdigit(c);c=getchar());
for(;isdigit(c);digit=digit*10+c-'0',c=getchar());
}
LL val[maxm],Sum[maxn],len[maxm];
int n,m,nC;
int nEdge=1,to[maxm],next[maxm],start[maxn];
int mat[70][maxm];
bool use[maxn];
void make(int a,int b,LL c)
{
++nEdge,to[nEdge]=b,next[nEdge]=start[a],len[nEdge]=c,start[a]=nEdge;
++nEdge,to[nEdge]=a,next[nEdge]=start[b],len[nEdge]=c,start[b]=nEdge;
}
void read()
{
Read(n),Read(m);
LL c;
for(int i=1,a,b;i<=m;++i)
{
Read(a),Read(b),Read(c);
make(a,b,c),make(b,a,c);
}
}
void DFS(int p)
{
use[p]=true;
for(int i=start[p];i;i=next[i])
{
int q=to[i];
if(use[q]==false)
Sum[q]=Sum[p]^len[i],DFS(q);
else
val[++nC]=Sum[p]^Sum[q]^len[i];
}
}
LL work()
{
sort(val+1,val+nC+1);
nC=unique(val+1,val+nC+1)-val-1;
for(int j=1;j<=60;++j)
{
mat[j][0]=~Sum[n]>>(j-1)&1;
for(int i=1;i<=nC;++i)
mat[j][i]=val[i]>>(j-1)&1;
}
LL ans=0;
for(int i=60;i>=1;--i)
{
ans<<=1;
int k=nC+1;
for(int j=1;j<=nC;++j)
if(mat[i][j])
{
k=j;
break;
}
if(k>nC)
{
if(mat[i][0]==0)
ans|=1;
continue;
}
ans|=1;
for(int j=i-1;j>=1;--j)
if(mat[j][k])
{
for(int p=0;p<=nC;++p)
mat[j][p]^=mat[i][p];
}
}
return ans;
}
int main()
{
read();
DFS(1);
printf("%lld\n",work());
work();
return 0;
}

  评论这张
 
阅读(290)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017