没学线性基今日考试爆炸的选手
为什么每次都是一考完发现刷题列表的下几个就是考的。。
线性基其实不难。。大概就是高斯消元一样的东西
这道题首先对第一个点dfs构一棵dfs树，那么上面会挂一些环
会发现在这个树上的xor有一个神奇的性质：选择其中的一个环并异或到当前异或和中，相当于反选了一些路径而用另外一些路径代替
那么答案就是在dfs树中n点到1点的异或和再异或上若干个环的异或和
这里犯了一个错误。。我允许了不选1到n的异或和。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
// <2115.cpp> - Wed Aug 3 16:26:56 2016 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } lol gl(){ lol res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=50010; const int MAXM=200010; const int INF=1e9; int bt=1,b[MAXN],next[MAXM],to[MAXM];lol val[MAXM]; inline void add(lol z,int y,int x){ next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z; next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=z; } bool vis[MAXN]; lol dis[MAXN],h[MAXM]; int tot; void dfs(int x,int f){ vis[x]=1; for(int i=b[x];i;i=next[i]){ if((i^f)==1)continue; if(vis[to[i]]){ if(i&1)h[++tot]=dis[x]^dis[to[i]]^val[i]; continue; } dis[to[i]]=dis[x]^val[i]; dfs(to[i],i); } } int main(){ int n=gi(),m=gi(); for(int i=1;i<=m;i++)add(gl(),gi(),gi()); dfs(1,0); lol ans=dis[n]; for(lol p=1ll<<62;p;p>>=1){ int fd=0; for(int i=1;i<=tot;i++) if(h[i]&p) if(fd)h[i]^=h[fd]; else fd=i; if(fd&&!(ans&p))ans^=h[fd]; h[fd]=0; } printf("%lld\n",ans); return 0; } |
说点什么