今天我刷题了吗
搜索文档…
倍增
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const int maxn(5e5 + 10);
7
const int maxm(1e6 + 10);
8
int ecnt, head[maxn];
9
int dep[maxn], f[maxn][20];
10
11
struct edge {
12
int to, nxt;
13
} edges[maxm];
14
15
template<typename T = int>
16
inline const T read()
17
{
18
T x = 0, f = 1;
19
char ch = getchar();
20
while (ch < '0' || ch > '9') {
21
if (ch == '-') f = -1;
22
ch = getchar();
23
}
24
while (ch >= '0' && ch <= '9') {
25
x = (x << 3) + (x << 1) + ch - '0';
26
ch = getchar();
27
}
28
return x * f;
29
}
30
31
template<typename T>
32
inline void write(T x, bool ln)
33
{
34
if (x < 0) {
35
putchar('-');
36
x = -x;
37
}
38
if (x > 9) write(x / 10, false);
39
putchar(x % 10 + '0');
40
if (ln) putchar(10);
41
}
42
43
void addEdge(int u, int v)
44
{
45
edges[ecnt].to = v;
46
edges[ecnt].nxt = head[u];
47
head[u] = ecnt++;
48
}
49
50
void bfs(int root)
51
{
52
queue<int> q;
53
q.push(root);
54
dep[root] = 1;
55
while (not q.empty()) {
56
int u = q.front();
57
q.pop();
58
for (int i = head[u]; compl i; i = edges[i].nxt) {
59
int v = edges[i].to;
60
if (dep[v]) {
61
continue;
62
}
63
q.push(v);
64
dep[v] = dep[u] + 1;
65
f[v][0] = u;
66
for (int j = 1; j < 20; ++j) {
67
f[v][j] = f[f[v][j - 1]][j - 1];
68
}
69
}
70
}
71
}
72
73
int lca(int u, int v)
74
{
75
if (dep[u] < dep[v]) {
76
swap(u, v);
77
}
78
for (int i = 19; i >= 0; --i) {
79
if (dep[f[u][i]] >= dep[v]) {
80
u = f[u][i];
81
}
82
}
83
if (u == v) {
84
return u;
85
}
86
for (int i = 19; i >= 0; --i) {
87
if (f[u][i] not_eq f[v][i]) {
88
u = f[u][i];
89
v = f[v][i];
90
}
91
}
92
return f[u][0];
93
}
94
95
int main()
96
{
97
#ifdef ONLINE_JUDGE
98
#else
99
freopen("input.txt", "r", stdin);
100
#endif
101
ios::sync_with_stdio(false);
102
memset(head, -1, sizeof head);
103
int n = read(), m = read(), s = read();
104
for (int i = 0; i < n - 1; ++i) {
105
int u = read(), v = read();
106
addEdge(u, v);
107
addEdge(v, u);
108
}
109
bfs(s);
110
while (m--) {
111
int u = read(), v = read();
112
write(lca(u, v), true);
113
}
114
return 0;
115
}
Copied!
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const double pi(acos(-1));
7
const int inf(0x3f3f3f3f);
8
const int maxn(1e6 + 10);
9
const int maxm(3e6 + 10);
10
int ecnt, head[maxn];
11
int pre[maxn], dep[maxn];
12
int f[maxn][17], d1[maxn][17], d2[maxn][17];
13
14
struct edge {
15
int u, v, w;
16
bool used;
17
18
bool operator <(const edge& rhs) const
19
{
20
return w < rhs.w;
21
}
22
} edges[maxm];
23
24
struct _edge {
25
int to, wt, nxt;
26
} _edges[maxm];
27
28
template<typename T = int>
29
inline const T read()
30
{
31
T x = 0, f = 1;
32
char ch = getchar();
33
while (ch < '0' || ch > '9') {
34
if (ch == '-') f = -1;
35
ch = getchar();
36
}
37
while (ch >= '0' && ch <= '9') {
38
x = (x << 3) + (x << 1) + ch - '0';
39
ch = getchar();
40
}
41
return x * f;
42
}
43
44
template<typename T>
45
inline void write(T x, bool ln)
46
{
47
if (x < 0) {
48
putchar('-');
49
x = -x;
50
}
51
if (x > 9) write(x / 10, false);
52
putchar(x % 10 + '0');
53
if (ln) putchar(10);
54
}
55
56
void addEdge(int u, int v, int w)
57
{
58
_edges[ecnt].to = v;
59
_edges[ecnt].wt = w;
60
_edges[ecnt].nxt = head[u];
61
head[u] = ecnt++;
62
}
63
64
int Find(int x)
65
{
66
return pre[x] == x ? x : pre[x] = Find(pre[x]);
67
}
68
69
void Union(int u, int v)
70
{
71
pre[Find(v)] = Find(u);
72
}
73
74
ll kruskal(int n, int m)
75
{
76
for (int i = 1; i <= n; ++i) {
77
pre[i] = i;
78
}
79
sort(edges, edges + m);
80
ll res = 0;
81
for (int i = 0; i < m; ++i) {
82
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
83
if (Find(u) != Find(v)) {
84
Union(u, v);
85
res += w;
86
edges[i].used = true;
87
}
88
}
89
return res;
90
}
91
92
void build(int m)
93
{
94
memset(head, -1, sizeof head);
95
for (int i = 0; i < m; ++i) {
96
if (edges[i].used) {
97
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
98
addEdge(u, v, w);
99
addEdge(v, u, w);
100
}
101
}
102
}
103
104
void bfs(int root)
105
{
106
dep[root] = 1;
107
queue<int> q;
108
q.push(root);
109
while (not q.empty()) {
110
int u = q.front();
111
q.pop();
112
for (int i = head[u]; compl i; i = _edges[i].nxt) {
113
int v = _edges[i].to, w = _edges[i].wt;
114
if (dep[v]) {
115
continue;
116
}
117
dep[v] = dep[u] + 1;
118
q.push(v);
119
f[v][0] = u;
120
d1[v][0] = w;
121
d2[v][0] = -inf;
122
for (int j = 1; j < 17; ++j) {
123
int anc = f[v][j - 1];
124
f[v][j] = f[anc][j - 1];
125
int dis[4] = { d1[v][j - 1], d2[v][j - 1], d1[anc][j - 1], d2[anc][j - 1] };
126
d1[v][j] = d2[v][j] = -inf;
127
for (int k = 0; k < 4; ++k) {
128
int d = dis[k];
129
if (d > d1[v][j]) {
130
d2[v][j] = d1[v][j];
131
d1[v][j] = d;
132
} else if (d not_eq d1[v][j] and d > d2[v][j]) {
133
d2[v][j] = d;
134
}
135
}
136
}
137
}
138
}
139
}
140
141
int lca(int u, int v, int w)
142
{
143
static int dis[maxn * 2];
144
int cnt = 0;
145
if (dep[u] < dep[v]) {
146
swap(u, v);
147
}
148
for (int i = 16; i >= 0; --i) {
149
if (dep[f[u][i]] >= dep[v]) {
150
dis[cnt++] = d1[u][i];
151
dis[cnt++] = d2[u][i];
152
u = f[u][i];
153
}
154
}
155
if (u not_eq v) {
156
for (int i = 16; i >= 0; --i) {
157
if (f[u][i] not_eq f[v][i]) {
158
dis[cnt++] = d1[u][i];
159
dis[cnt++] = d2[u][i];
160
dis[cnt++] = d1[v][i];
161
dis[cnt++] = d2[v][i];
162
u = f[u][i];
163
v = f[v][i];
164
}
165
}
166
dis[cnt++] = d1[u][0];
167
dis[cnt++] = d1[v][0];
168
}
169
int dis1 = -inf, dis2 = -inf;
170
for (int i = 0; i < cnt; ++i) {
171
int d = dis[i];
172
if (d > dis1) {
173
dis2 = dis1;
174
dis1 = d;
175
} else if (d not_eq dis1 and d > dis2) {
176
dis2 = d;
177
}
178
}
179
if (w > dis1) {
180
return w - dis1;
181
}
182
if (w > dis2) {
183
return w - dis2;
184
}
185
return inf;
186
}
187
188
int main()
189
{
190
#ifdef ONLINE_JUDGE
191
#else
192
freopen("input.txt", "r", stdin);
193
#endif
194
ios::sync_with_stdio(false);
195
int n = read(), m = read();
196
for (int i = 0; i < m; ++i) {
197
int u = read(), v = read(), w = read();
198
addEdge(u, v, w);
199
edges[i] = edge{ u, v, w };
200
}
201
ll sum = kruskal(n, m);
202
build(m);
203
bfs(1);
204
ll res = 1e18;
205
for (int i = 0; i < m; ++i) {
206
if (not edges[i].used) {
207
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
208
res = min(res, sum + lca(u, v, w));
209
}
210
}
211
write(res, true);
212
return 0;
213
}
Copied!
最近更新 1yr ago
复制链接