This page looks best with JavaScript enabled

「WC2011」最大XOR路径-dfs+线性基

 ·  ✏️ About  623 words  ·  ☕ 2 mins read · 👀... views

考虑一个边权为非负整数的无向连通图,节点编号为 $1$ 到 $N$ ,试求出一条从 $1$ 号节点到 $N$ 号节点的路径,使得路径上经过的边的权值的 $\text{XOR}$ 和最大。

路径可以重复经过某些点或边,当一条边在路径中出现了多次时,其权值在计算 $\text{XOR}$ 和时也要被计算相应多的次数。

图中可能有重边或自环。

链接

Luogu P4151

题解

一个有可能比较常见的套路:

考虑 $1\rightarrow n$ 的路径,一定由一条路径和一些环获得。

我们注意到考虑挂在路径上的环的影响时,不必考虑环如何到达路径,因为我们必然有一条路径使得“去环”和“离开环”恰好抵消。因此我们可以随便加环。

我们甚至还注意到,$1\rightarrow n$ 路径也可以随便选,因为如果是另一条路径的话,事实上异或一个经过 $1$ 和 $n$ 的大环就可以得到另一条 $1 \rightarrow n$ 的路径了。

找环就用 dfs ,其中每一条返祖边都可以对应一个环。即使是有公共边的环也可以用小环异或出来,所以返祖边直接处理环即可。

时间复杂度 $O(n \times 64)$.

代码

 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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
using namespace std;

typedef long long ll;

const int MAXN = 51000,MAXM = 110000,logn = 61;

struct LB{
  ll basis[logn];
  void insert(ll x){
    if(!x) return;
    for(int i = logn-1;i>=0;--i){
      if((x & (1LL<<i)) == 0) continue;
      if(basis[i] == 0){
        basis[i] = x;
        break;
      }
      else{
        x ^= basis[i];
      }
    }
  }
  ll getmax(ll ans = 0){
    for(int i = logn-1;i>=0;--i){
      if((ans^basis[i]) > ans){
        ans ^= basis[i];
      }
    }
    return ans;
  }
}B;

struct Edge{
  int to,nex;
  ll len;
}edge[MAXM*2];
int fir[MAXN],ecnt = 2;
void addedge(int a,int b,ll c){
  edge[ecnt] = (Edge){b,fir[a],c};
  fir[a] = ecnt++;
}

int n,m;

void init(){
  scanf("%d %d",&n,&m);
  int a,b;ll c;
  for(int i = 1;i<=m;i++){
    scanf("%d %d %lld",&a,&b,&c);
    addedge(a,b,c);
    addedge(b,a,c);
  }
}

ll dis[MAXN];bool vis[MAXN];


void dfs(int nown){
  vis[nown] = 1;
  for(int nowe = fir[nown];nowe;nowe = edge[nowe].nex){
    int v = edge[nowe].to;ll len = edge[nowe].len;
    if(vis[v] == 1){
      B.insert(dis[nown]^dis[v]^len);
    }
    else{
      dis[v] = dis[nown] ^ len;
      dfs(v);
    }
  }
}

void solve(){
  dfs(1);
  printf("%lld\n",B.getmax(dis[n]));
}

int main(){
  init();
  solve();
  return 0;
}

cqqqwq
WRITTEN BY
cqqqwq
A student in Computer Science.

评论: