亦或最短路

ACM

花费为边权的亦或值

洛谷4366

link
给出m条边，它们之间的权重。
然后任意两点之间可以通过，花费为节点编号的亦或值。

题解

通过值的拆解，建立新的图来求解
3^6 = 5 = (4+1)
(3^7)+(7^6) = 4+1
那么连边的节点为(3^4)和(6^1),//亦或的结合律
题解报告

ac code

建立新的图然后跑最短路就可以了

亦或的最短路、最长路

亦或求最长路
亦或求最短路

code

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
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N=100005;
int n,m;
int head[N],tot;
struct aa
{
	int to,pre;ll dis;
}edge[N*2];
void addedge(int u,int v,ll d)
{
	edge[++tot].to=v;edge[tot].pre=head[u];edge[tot].dis=d;head[u]=tot;
}
int dfn[N],cnt;
ll f[N],tmp[N*2],num;
void dfs(int u,int fa)
{
	dfn[u]=++cnt;
	for (int v,i=head[u];i;i=edge[i].pre)
	if ((v=edge[i].to)!=fa)
	{
		if (dfn[v]==0)
		{
			f[v]=f[u]^edge[i].dis;
			dfs(v,u);
		}
		else tmp[++num]=f[u]^f[v]^edge[i].dis;
	}
}
ll b[65];
int main()
{
	scanf("%d%d",&n,&m);
	int u,v;ll d;
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d%I64d",&u,&v,&d);
		addedge(u,v,d);
		addedge(v,u,d);
	}
	dfs(1,0);
	//求出线性基
	for (int i=1;i<=num;i++)
	{
		for (int j=62;j>=0;j--) if ((tmp[i]>>j)&1)
		{
			if (b[j]) tmp[i]^=b[j];
			else {b[j]=tmp[i];break;}
		}
	}
    //用基和一条路径进行亦或，从而求最长路
	for (int i=62;i>=0;i--)
	if ((f[n]^b[i])<f[n]) f[n]=f[n]^b[i];
	printf("%I64d",f[n]);
	return 0;
}

未解决的问题

本文标题:亦或最短路

文章作者:Babydragon

发布时间:2018-06-08, 00:21:39

最后更新:2018-06-08, 21:05:20

原始链接:http://baolintian.github.io/2018/06/08/亦或最短路/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 洛谷4366
    1. 1.1. 题解
    2. 1.2. ac code
  2. 2. 亦或的最短路、最长路
    1. 2.1. code
  3. 3. 未解决的问题
{{ live2d() }}