水题笔记_Noip2013 货车运输 [LCA]

有的时候需要转换给定的图(比如转成树)

懵逼的 题目

传送至 Codevs
大意:给定一个无向图 求两点之间的最大的最小值
(然而这题gty学长在夏令营讲过我还崩了三天…还不如初中没学oi的dalao们QAQ宽嫂怕不是坏掉了QAQ)

扯淡的 题解

数据范围太大…SPFA只有60…因为是求最大的最小值…又不能同时走两条路(否则估计就是网络流板子了?) 所以如果两点之间有两条路 我们就可以只保留大的…这样就把图转化为了一棵最大生成树…就可以跑nlogn的LCA了…
又及:LCA写挂了两天…一个是初始化数组名字混了(5分没了)…(趴) 一个是倍增跳到同一深度时没有检查是否已经是一个点了(90分没了)…(趴…惨痛教训…)

沙茶的 代码

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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
//http://codevs.cn/problem/3287/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MAXN (10000 + 5)
#define MAXM (50000 + 5)
#define MAXL (15 + 5)
#define INF (0x7ffffff)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define swap(a, b) {int t = a; a = b; b = t;}
using namespace std;
vector<int> root;
struct edgg
{
int from;
int to;
int cost;
}a[MAXM];// kruskal's edge
struct edgt
{
int to;
int cost;
int next;
}b[MAXN * 2];// tree's edge
int cntm = 0;// add a edge
int cntc = 0;// add a kind of color
int lgn;
int n;// number of nodes
int m;// number of edges
int g[MAXN];// vector
int f[MAXN];// bcj
int fa[MAXN];// fa[i] means i's father is f[i]
int d[MAXN][MAXL];// lca
int deep[MAXN];// deep in its tree
int minc[MAXN][MAXL];// the min cost in the road
int col[MAXN];// a node's color
int lg(int);
bool cmp(edgg, edgg);
void adn(int, int, int);// add a edge
int find(int);
void uni(int, int);
void kruskal();
void dfs(int, int);// inint
int lca(int, int);
int main()
{
memset(col, 0, sizeof(col));
scanf("%d%d", &n, &m);
lgn = lg(n);
int srx, sry, srz;
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d", &a[i].from, &a[i].to, &a[i].cost);
}
kruskal();
for (int i = 1; i <= n; i++)
{
if (!col[i])
{
root.push_back(i);
fa[i] = d[i][0] = i;
minc[i][0] = INF;
col[i] = ++cntc;
dfs(i, 1);
}
}
/*for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= lgn; j++)
{
printf("%d ",minc[i][j]);
}
puts("");
}*/
int q;
scanf("%d", &q);
for (int i = 1; i <= q; i++)
{
scanf("%d%d", &srx, &sry);
if (col[srx] != col[sry])
{
puts("-1");
}
else
{
printf("%d\n", lca(srx, sry));
}
}
return 0;
}
void adn(int f, int t, int c)
{
b[++cntm].next = g[f];
b[cntm].to = t;
b[cntm].cost = c;
g[f] = cntm;
}
int lg(int x)
{
int re = 0;
int i = 0;
for(;re <= x; i++)
{
re = (1 << i);
}
return i;
}
bool cmp(edgg x, edgg y)
{
return x.cost > y.cost;
}
int find(int x)
{
return x == f[x] ? x : (f[x] = find(f[x]));
}
void uni(int x, int y)
{
int fx = find(x);
int fy = find(y);
f[fx] = fy;
}
void kruskal()
{
for (int i = 1; i <= n; i++)
{
f[i] = i;
}
sort(a + 1, a + m + 1, cmp);
int cntb = 0;
for (int i = 1; i <= m; i++)
{
if (cntb == n - 1)
{
break;
}
int fx = find(a[i].from); int fy = find(a[i].to);
if (fx != fy)
{
adn(a[i].from, a[i].to, a[i].cost);
adn(a[i].to, a[i].from, a[i].cost);
uni(fx, fy);
++cntb;
}
}
}
void dfs(int dq, int de)
{
col[dq] = cntc;
deep[dq] = de;
for (int i = 1; i <= lgn; i++)
{
d[dq][i] = d[d[dq][i - 1]][i - 1];
minc[dq][i] = min(minc[dq][i - 1], minc[d[dq][i - 1]][i - 1]);
}
for (int i = g[dq]; i; i = b[i].next)
{
if (b[i].to != fa[dq])
{
d[b[i].to][0] = fa[b[i].to] = dq;
minc[b[i].to][0] = b[i].cost;
dfs(b[i].to, de + 1);
}
}
}
int lca(int x, int y)
{
if (deep[x] < deep[y])
{
swap(x, y);
}
int re = INF;
for (int i = lgn; i >= 0; i--)
{
if (deep[x] == deep[y])
{
break;
}
if (deep[d[x][i]] >= deep[y])
{
re = min(re, minc[x][i]);
x = d[x][i];
}
}
if (x == y)
return re;
for (int i = lgn; i >= 0; i--)
{
if (d[x][i] != d[y][i])
{
re = min(re, min(minc[x][i], minc[y][i]));
x = d[x][i];
y = d[y][i];
}
}
return min(re, min(minc[x][0], minc[y][0]));
}
/*
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
*/

By win10被可怕学弟搞崩还逃不了军训的可怜 Cansult