2018 ICPC XuZhou Online J Maze Designer

Posted on | In

题目链接

题意不太能说清楚，于是直接上结论吧，代码略丑。

Solution:

将squares看作点，相邻两个square之间连一条权值为建墙费用的边，若任意两点间只有唯一路径相连，
则该图必然是一棵树， 于是求两点间最短距离即为求两结点在最大生成树上的距离。

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e5 + 5;
const int maxm = 8e5 + 5;

// 原图上的边
struct EDGE {
    int u, v, w;
    EDGE(int uu = 0, int vv = 0, int ww = 0) : u(uu), v(vv), w(ww) {}
    bool operator< (const EDGE& b) const {
        return w > b.w;
    }
}E[maxm];

// 生成树上的边
struct edge {
    int v, next;
    edge(int vv = 0, int nxt = -1) : v(vv), next(nxt) {}
}e[maxm];

int n;
int totE, tot;
int fa[maxn], head[maxn];

int dep[maxn], dp[maxn][20], maxb;

void init() {
    totE = tot = 0;
    for (int i = 1; i < maxn; i++) {
        head[i] = -1, dep[i] = 0, fa[i] = i;
        memset(dp[i], -1, sizeof dp[i]);
    }
}

void addEDGE(int u, int v, int w) {
    E[totE++] = EDGE(u, v, w);
}

void addedge(int u, int v) {
    e[tot] = edge(v, head[u]); head[u] = tot++;
    e[tot] = edge(u, head[v]); head[v] = tot++;
}

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

// Kruskal求最大生成树
void kruskal() {
    sort(E, E + totE);
    for (int i = 0; i < totE; i++) {
        int u = E[i].u, v = E[i].v;
        if (find(u) != find(v)) {
            fa[fa[v]] = fa[u];
            addedge(u, v);
        }
    }
}

// 倍增法求LCA
void DFS(int u, int pre) {
    dp[u][0] = pre;
    dep[u] = dep[pre] + 1;
    for (int i = head[u]; i != -1; i = e[i].next) {
        if (e[i].v != pre) {
            DFS(e[i].v, u);
        }
    }
}

void makedp() {
    for (maxb = 0; (1 << maxb) <= n; ++maxb);
    for (int j = 1; j < maxb; j++) {
        for (int i = 1; i <= n; i++) {
            if (~dp[i][j - 1]) {
                dp[i][j] = dp[dp[i][j - 1]][j - 1];
            }
        }
    }
}

int LCA(int u, int v) {
    if (dep[u] < dep[v]) {
        swap(u, v);
    }
    for (int j = maxb - 1; ~j; --j) {
        if (dep[dp[u][j]] >= dep[v]) {
            u = dp[u][j];
        }
    }
    if (u == v) return u;
    for (int j = maxb - 1; ~j; --j) {
        if (dp[u][j] != dp[v][j]) {
            u = dp[u][j], v = dp[v][j];
        }
    }
    return dp[u][0];
}

int main() {
    init();
    int n1, m; scanf("%d%d", &n1, &m);
    n = n1 * m;
    for (int i = 1; i <= n; i++) {
        char s[3]; int x;
        scanf("%s%d", s, &x);
        if (s[0] == 'D' && i + n1 <= n) {
            addEDGE(i, i + n1, x);
        }
        if (s[0] == 'R' && i + 1 <= n) {
            addEDGE(i, i + 1, x);
        }
        scanf("%s%d", s, &x);
        if (s[0] == 'D' && i + n1 <= n) {
            addEDGE(i, i + n1, x);
        }
        if (s[0] == 'R' && i + 1 <= n) {
            addEDGE(i, i + 1, x);
        }
    }
    kruskal();

    dep[0] = -1;
    DFS(1, 0);
    makedp();

    int q; scanf("%d", &q);
    while (q--) {
        pair<int, int> p1, p2;
        scanf("%d%d%d%d", &p1.first, &p1.second, &p2.first, &p2.second);
        int u = (p1.first - 1) * m + p1.second, v = (p2.first - 1) * m + p2.second;
        if (u == v) {
            printf("0\n");
            continue;
        }
        int lca = LCA(u, v);
        printf("%d\n", dep[u] + dep[v] - 2 * dep[lca]);
    }
}