锐客网

  1. 首页 > it技术 > >

845G|845G - Shortest Path Problem?（线性基）

845G - Shortest Path Problem?
题意：给一个树，求1到n的最短路径。这里的路径定义为异或和。
845G|845G - Shortest Path Problem?（线性基）
文章图片


线性基~
845G|845G - Shortest Path Problem?（线性基）
文章图片
845G|845G - Shortest Path Problem?（线性基）
文章图片

1 #include 2 using namespace std; 3 #define ll long long 4 struct LiBase{ 5ll a[63]; 6//初始化 7void init(){ 8memset(a,0,sizeof(a)); 9} 10//插入 11bool insert_(ll x){ 12for(int i=62; i>=0&&x; i--)if(x&(1LL<0; 19} 20//最大 21ll query_min(ll x){ 22ll ans=x; 23for(int i=62; i>=0; i--){ 24if((ans^a[i])a[i]; 25} 26return ans; 27} 28 }; 29 const int maxv=100010; 30 const int maxe=100010; 31 int head[maxv]; 32 int cnt=0; 33 struct Edge{ 34int v,nex; 35ll w; 36Edge(int v=0,ll w=0,int nex=0):v(v),w(w),nex(nex){} 37 }e[maxe<<1]; 38 void init(){ 39cnt=0; 40memset(head,-1,sizeof(head)); 41 } 42 void add(int u,int v,ll w){ 43e[cnt]=Edge(v,w,head[u]); 44head[u]=cnt++; 45e[cnt]=Edge(u,w,head[v]); 46head[v]=cnt++; 47 } 48 49 LiBase lb; 50 int n,m; 51 int dfsk; 52 ll dis[maxv],pre[maxv]; 53 54 void dfs(int u,int id){ 55pre[u]=++dfsk; 56for(int i=head[u]; ~i; i=e[i].nex){ 57if(i==(id^1)) continue; 58int v=e[i].v; 59if(!pre[v]){ 60dis[v]=e[i].w^dis[u]; 61dfs(v,i); 62}else if(pre[v]
dis[v]); 63} 64 } 65 66 void get_cir(){ 67memset(pre,0,sizeof(pre)); 68memset(dis,0,sizeof(dis)); 69dfsk=0; 70dfs(1,-1); 71 } 72 int main(){ 73while(scanf("%d%d",&n,&m)!=EOF){ 74int u,v; 75ll w; 76init(); lb.init(); 77for(int i=0; i
View Code 【845G|845G - Shortest Path Problem?（线性基）】
转载于:https://www.cnblogs.com/yijiull/p/7425490.html

    推荐阅读


    上一篇：牛客网_Wannafly模拟赛1

    下一篇：slf4j，log4j，logback之间的关系