Codeforces 845G Shortest Path Problem?

时间:2025-01-11 09:34:56

http://codeforces.com/problemset/problem/845/G

从顶点1dfs全图,遇到环则增加一种备选方案,环上的环不需要走到前一个环上作为条件,因为走完第二个环可以从第一个环原路返回。
对每种备选方案通过x = min(x,x^v[i]) 保留备选方案中不存在的最高位,如果能由已经存在的备选方案组合得到则结果为零
最后对val[n]做一次类似的操作得到答案
#include<bits/stdc++.h>
using namespace std;
const int maxn = ;
vector<int> v;
struct EDGE{
int to,next,len;
EDGE(){
}
EDGE(int a,int b,int c){
to = a,next = b,len = c;
}
}e[maxn<<];
int vis[maxn],st,ed,cnt,head[maxn],val[maxn],len;
void add(int u,int v,int len){
e[++cnt] = EDGE(v,head[u],len);
head[u] = cnt;
}
void add(int x){
for(int i = ;i<(int)v.size();i++){
x = min(x,x^v[i]);
}
if(x) v.push_back(x);
}
void dfs(int x,int now){
vis[x] = ;
for(int i = head[x];i;i = e[i].next){
int to = e[i].to;
if(vis[to]) add(val[to]^now^e[i].len);
else{
val[to] = now^e[i].len;
dfs(to,val[to]);
}
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i = ;i<m;i++){
scanf("%d%d%d",&st,&ed,&len);
add(st,ed,len);
add(ed,st,len);
}
dfs(,);
for(int i = ;(int)i<v.size();i++){
val[n] = min(val[n],val[n]^v[i]);
}
return *printf("%d",val[n]);
}

8/28更新

https://csacademy.com/contest/archive/task/xor_cycle

一道类似的题,同样是找出所有环,最后组合出最大结果输出即可

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n,m;
vector<pair<int,long long> > node[];
int vis[],a,b;
long long val[];
long long _len;
vector<long long> base;
void add(long long x){
for(int i = ;i<base.size();i++){
x = min(x,x^base[i]);
}
if(x) base.push_back(x);
}
void dfs(int x,int fa){
for(int i = ;i<node[x].size();i++){
int to = node[x][i].first;
long long len = node[x][i].second;
if(to == fa) continue;
if(!vis[to]){
vis[to] = ;
val[to] = val[x]^len;
dfs(to,x);
}
else{
add(val[to]^len^val[x]);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie();
cin>>n>>m;
for(int i = ;i<m;i++){
cin>>a>>b>>_len;
node[a].push_back(make_pair(b,(long long)_len));
node[b].push_back(make_pair(a,(long long)_len));
}
dfs(,-);
long long ans = ;
for(int i = ;i<base.size();i++){
ans = max(ans,ans^base[i]);
}
cout<<ans<<endl;
return ;
}