DDOSvoid's Blog

某场模拟赛 walk

发表于 更新于 分类于
本文字数： 3.5k 阅读时长 ≈ 3 分钟

题目描述

简要题意：给定一个边权均为 $1$ 的有向图，如果 $a_i~and~a_j=a_j$，则有一条 $i$ 连向 $j$ 的边，额外再给 $m$ 条有向边，求 $1$ 到其它所有点的最短路

$n\le 2\times 10^5,m\le 3\times 10^5,1\le a_i < 2^{20}$​​

Solution

一个显然的思路是建 $2^{20}$​ 个点，然后每个点向自己的子集连边，复杂度 $O(3^{20})$​ 爆炸

考虑优化边的数量，每个点只向自己去掉一个二进制一个 $1$ 的点连边，这样复杂度 $O(20\cdot 2^{20})$

用 $0-1~bfs$ 即可

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define maxn 200010
#define maxm 300010
#define Maxn 1048576
#define INF 1000000000
using namespace std;

int n, m, a[maxn], s; 

struct Edge {
    int to, next, w;
} e[maxm + maxn + Maxn * 20]; int c1, head[maxn + Maxn];
inline void add_edge(int u, int v, int w) {
    e[c1].to = v; e[c1].w = w;
    e[c1].next = head[u]; head[u] = c1++;
}

deque<int> Q; int dis[Maxn + maxn]; bool vis[maxn + Maxn];
void bfs() {
    Q.push_front(s);
    for (int i = 0; i < Maxn + maxn; ++i) dis[i] = INF; dis[s] = 0; 
    while (!Q.empty()) {
        int u = Q.front(); Q.pop_front();
        if (vis[u]) continue; vis[u] = 1; 
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (w) Q.push_back(w);
                else Q.push_front(w);
            }
        }
    }
}

int main() { memset(head, -1, sizeof head);
    cin >> n >> m; s = 1;
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= m; ++i) {
        int x, y; scanf("%d%d", &x, &y);
        add_edge(x, y, 1);
    } int M = (1 << 20) - 1; 
    for (int i = 1; i <= M; ++i)
        for (int j = 0; j < 20; ++j) { 
            if (i >> j & 1 == 0) continue;
            if (i ^ 1 << j == 0) continue ;
            add_edge(n + i, n + (i ^ 1 << j), 0); 
        }
    for (int i = 1; i <= n; ++i) { 
        add_edge(n + a[i], a[i], 1);
        add_edge(a[i], n + a[i], 0);
    }
    bfs();
    for (int i = 2; i <= n; ++i) {
        if (dis[i] == INF) puts("-1");
        else printf("%d\n", dis[i]);
    }
    return 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
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define maxn 200010
#define maxm 300010
#define INF 1000000000
using namespace std;

int n, m;

int a[maxn];

const int N = 20;
const int M = (1 << N) - 1;

struct Edge{
    int to, next, w;
}e[maxm + maxn + 20 * M]; int c1, head[maxn + M];
inline void add_edge(int u, int v, int w){
    e[c1].to = v; e[c1].w = w;
    e[c1].next = head[u]; head[u] = c1++;
}

int dis[maxn + M];
void mem(){
    for(int i = 0; i < maxn + M; ++i) dis[i] = INF;
}

deque<int> Q; bool vis[maxn + M];
void bfs(){
    mem();
    Q.push_back(1); dis[1] = 0;
    while(!Q.empty()){
        int u = Q.front(); Q.pop_front();
        if(vis[u]) continue; vis[u] = 1;
        for(int i = head[u]; ~i; i = e[i].next){
            int v = e[i].to, w = e[i].w;
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                cout << v << " " << u << endl;
                if(w) Q.push_back(v);
                else Q.push_front(v);
            }
        }
    }
}

int main(){
    freopen("walk.in", "r", stdin);
    freopen("walk.out", "w", stdout);
    memset(head, -1, sizeof head);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 1; i <= m; ++i){
        int x, y; scanf("%d%d", &x, &y);
        add_edge(x, y, 1); 
    }
    for(int i = 1; i <= n; ++i){
        add_edge(i, n + a[i], 0), add_edge(n + a[i], i, 1);
        cout << i << " " << n + a[i] << endl;
    }
    for(int i = 1; i <= M; ++i)
        for(int j = 0; j < N; ++j)
            if(i >> j & 1){
                if(!(i ^ 1 << j)) continue;
                add_edge(n + i, n + (i ^ 1 << j), 0);
            }
    bfs();
    for(int i = 1; i <= n; ++i){
        if(dis[i] == INF) puts("-1");
        else printf("%d ", dis[i]);
    }
    return 0;
}