邢台天九建设有限公司网站,wordpress中文开发电子书,网站定制技术,网站建设的流程视频正题
题目链接:https://www.luogu.com.cn/problem/P4151 题目大意
给一个无向图#xff0c;求一条1∼n1\sim n1∼n的路径使得异或和最大。 解题思路
很强的思路啊#xff08;好像去年YPXYPXYPX大爷就讲了反正我也没听懂#xff09;
我们可以将路径拆分成三部分#xff…正题
题目链接:https://www.luogu.com.cn/problem/P4151 题目大意
给一个无向图求一条1∼n1\sim n1∼n的路径使得异或和最大。 解题思路
很强的思路啊好像去年YPXYPXYPX大爷就讲了反正我也没听懂
我们可以将路径拆分成三部分环连接环的路径连接111和nnn的路径。其中连接环的路径因为会走两次所以就不用处理。
那我们发现如果111点能到的环可以任意我们选择异或或者不异或也就是对于每个环我们可以丢入线性基中处理。
考虑111到nnn的路径如何选择我们发现对于两条111到nnn的路径会构成一个环也就是如果我们选择了不优的那一条那么只要异或上这个大环就可以了。所以我们随便选择一条111到nnn的路径即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N5e410;
struct node{ll to,next,w;
}a[N*4];
ll n,m,tot,d[80],v[N],w[N],ls[N];
void add(ll x){for(ll i60;i0;i--)if((xi)1){if(d[i])x^d[i];else{d[i]x;break;}}return;
}
void addl(ll x,ll y,ll w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;return;
}
void dfs(ll x,ll dis){v[x]1;w[x]dis;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(v[y])add(dis^a[i].w^w[y]);else dfs(y,dis^a[i].w);}//v[x]0;return;
}
ll solve(ll ans){for(ll i60;i0;i--)if((ans^d[i])ans)ans^d[i];return ans;
}
int main()
{scanf(%lld%lld,n,m);for(ll i1;im;i){ll x,y,w;scanf(%lld%lld%lld,x,y,w);addl(x,y,w);addl(y,x,w);}dfs(1,0);printf(%lld,solve(w[n]));
}
