企业网站建设如何去规划/seo 页面

http://www.lydsy.com/JudgeOnline/problem.php?id=2115

 

边和点可以重复经过，那最后的路径一定是从1到n的一条路径加上许多环

dfs出任意一条路径的异或和、路径上所有环的异或和，加入线性基即可

 

#include<cstdio>
#include<iostream>using namespace std;#define N 50001
#define M 100001typedef long long LL;int n;int tot,front[N],to[M<<1],nxt[M<<1];
LL val[M<<1];bool vis[N];int cnt;
LL dis[N];
LL a[M<<2];LL b[61];template<typename T>
void read(T &x)
{x=0; char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}void add(int u,int v,LL w)
{to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w;to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; val[tot]=w;
}void dfs(int x,int y)
{vis[x]=true;for(int i=front[x];i;i=nxt[i])if(to[i]!=y){if(!vis[to[i]]) dis[to[i]]=dis[x]^val[i],dfs(to[i],x);else a[++cnt]=dis[to[i]]^dis[x]^val[i];}
}void solve()
{for(int i=1;i<=cnt;++i)for(int j=60;j>=0;--j)if(a[i]>>j&1){if(!b[j]){b[j]=a[i];break;}a[i]^=b[j];}LL ans=dis[n];for(int i=60;i>=0;--i)if((ans^b[i])>ans) ans^=b[i];cout<<ans;
}int main()
{int m;read(n); read(m);int u,v;LL w;while(m--){read(u); read(v); read(w);add(u,v,w);}dfs(1,0);solve();return 0;
}

 

2115: [Wc2011] Xor

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

6

HINT