最小OR路径(按位贪心)

描述

传送门:EOJ Monthly 2018.1 - Problem F

给定一个有 $n$ 个点和 $m$ 条边的无向图,其中每一条边 $e_i$ 都有一个权值记为 $w_i$。

对于给出的两个点 $a$ 和 $b$,求一条 $a$ 到 $b$ 的路径,使得路径上的边权的 $OR$(位或)和最小,输出这个值。(也就是说,如果将路径看做边的集合 $\lbrace e_1,e_2,…,e_k \rbrace$,那么这条路径的代价为 $w_1ORw_2OR…ORw_k$,现在求一条路径使得其代价最小,输出这个代价。) 如果不存在这样的路径,输出 $−1$。

Input

第一行两个数 $n$ 和 $m$。
接下来 $m$ 行,每行三个数 $u_i$,$v_i$,$w_i$,表示有一条 $u_i$ 到 $v_i$ 的权值为 $w_i$ 的无向边。
最后一行两个数 $a$,$b$,分别表示起点和终点。

$2≤n≤10 ^ 4$,$0≤m≤10 ^ 6$,$0≤c_i≤2 ^ {62}−1$
$1≤u_i,v_i,a,b≤n$,$a≠b$
可能有重边和自环。

Output

在一行中输出一个最小代价,如果无解输出 $−1$。

Examples

  • input
1
2
3
4
5
6
3 4
1 2 2
1 2 4
1 3 5
2 3 3
1 2
  • output
1
2

思路

  • 首先这题我们不能像求解最短路那样去贪心地寻找。
  • 假设答案的二进制位全是$1$,然后从高位到低位考虑,如果将该位置为$0$不破坏连通性的话就置为 0,这样肯定最优。
  • 具体实现也很简单……把当前位为$0$的边拿出来搞一遍并查集就好。

代码

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
82
83
84
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

typedef pair<ll, PII> Edge;
vector<Edge> G;
vector<Edge> tG;
const int N = 10005;
int fa[N];

inline void init(int n)
{
for (int i = 0; i <= n; i++) fa[i] = i;
}

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void unite(int x, int y)
{
x = find(x), y = find(y);
if (x == y) return;
fa[y] = x;
}

bool same(int x, int y) { return find(x) == find(y); }

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
fastin
int n, m, s, t;
cin >> n >> m;
init(n);
while (m--)
{
static int u, v;
ll c;
cin >> u >> v >> c;
G.pb(mp(c, mp(u, v)));
unite(u, v);
}
cin >> s >> t;
if (!same(s, t))
{
cout << -1 << endl;
return 0;
}
ll ans = (1LL << 62) - 1;
for (int i = 61; ~i; i--)
{
init(n);
for (auto& e : G)
{
ll w = e.X;
int u = e.Y.X, v = e.Y.Y;
if (!(w >> i & 1)) unite(u, v), tG.pb(mp(w, mp(u, v)));
}
if (same(s, t))
{
ans ^= (1LL << i);
swap(G, tG);
}
tG.clear();
}
cout << ans << endl;
return 0;
}
捐助作者