NOIP2013 Day1 T3(最大生成树+树链剖分/最大生成树+倍增)

一看题目就想树剖,但是这里是图,怎么办?用最小生成树。我们只需要用最大的那几条边来连接这些点成为一棵树,其他的边是没有用的。求完最大树以后,再树链剖分或者倍增思想,这里没有做倍增只做了树剖,注意树剖的时候边权转点权,边权放到深度深的那个点上,然后处理每一个路径$(u,v)$,对于$LCA(u,v)$是不用加的!刚开始正解和暴力全部写挂这里直接10分。改了之后发现暴力还比正解快500ms。。下面给出树剖代码和暴力代码,以及数据生成器,有用的可以拿去。

树剖:

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 10000 + 5, MAXM = 50000 + 5, INF = 1000000000;
struct data1 {
int u, v, wi;
bool operator < (const data1 &x) const {
return wi > x.wi;
}
}e1[MAXM];//原图
struct data2 {
int v, wi;
}e2[MAXM*2];//最大树
int n, m, Q, en, f[MAXN];//最大树边数,并查集
int dwi[MAXN], dep[MAXN], fa[MAXN], top[MAXN], p[MAXN], siz[MAXN], son[MAXN], pre;//树剖
int minv[MAXN*4];//线段树
vector<int> G[MAXN];//最大树
#define lc (o<<1)
#define rc (o<<1|1)
#define M ((l+r)>>1)
void pushup(int o) {//线段树
minv[o] = min(minv[lc], minv[rc]);
}
void update(int o, int l, int r, int p, int v) {//线段树
if (l==r) {
minv[o] = v;
return ;
}
if (p<=M) update(lc, l, M, p, v);
else if (M<p) update(rc, M+1, r, p, v);
pushup(o);
}
int query(int o, int l, int r, int x, int y) {//线段树
int ret = INF;
if (x<=l&&r<=y) {
return minv[o];
}
if (x<=M) ret = min(ret, query(lc, l, M, x, y));
if (M<y) ret = min(ret, query(rc, M+1, r, x, y));
return ret;
}
int find(int x) {return x==f[x] ? x : f[x] = find(f[x]);}//并查集find
void dfs1(int u, int pa) {//树剖
dep[u] = dep[pa] + 1, fa[u] = pa, siz[u] = 1;
for (int i=0;i<G[u].size();i++) {
data2 d2 = e2[G[u][i]];
int v = d2.v, wi = d2.wi;
if (v!=pa) {
dfs1(v, u);
dwi[v] = wi;
siz[u] += siz[v];
if (son[u]==-1||siz[v]>siz[son[u]]) son[u] = v;
}
}
}
void dfs2(int u, int cha) {//树剖
top[u] = cha, p[u] = ++pre;
if (son[u]!=-1) {
dfs2(son[u], cha);
for (int i=0;i<G[u].size();i++) {
data2 d2 = e2[G[u][i]];
int v = d2.v;
if (v!=fa[u]&&v!=son[u]) {
dfs2(v, v);
}
}
}
}
int findMax(int u, int v) {//树剖
int ret = INF, f1 = top[u], f2 = top[v];
while (f1!=f2) {
if (dep[f1]<dep[f2]) swap(f1, f2), swap(u, v);
ret = min(ret, query(1,1,n,p[f1],p[u]));
u = fa[f1];
f1 = top[u];
}
if (dep[u]<dep[v]) swap(u, v);
return min(ret, query(1,1,n,p[v]+1,p[u]));
}
void MST() {//Kruskal
sort(e1+1, e1+1+m);
for (int i=1;i<=m;i++) {
int a1 = find(e1[i].u), b1 = find(e1[i].v);
if (a1==b1) continue;
f[a1] = b1;
en++, e2[en].v = e1[i].v, e2[en].wi = e1[i].wi, G[e1[i].u].push_back(en);
en++, e2[en].v = e1[i].u, e2[en].wi = e1[i].wi, G[e1[i].v].push_back(en);
}
}
void clean() {
pre = en = 0;
for (int i=0;i<=n;i++) {
dep[i] = fa[i] = top[i] = p[i] = siz[i] = 0;
son[i] = -1;
f[i] = i;
G[i].clear();
}
for (int i=0;i<=4*n;i++) minv[i] = INF;
}
void init() {
clean();
for (int i=1;i<=m;i++) {
scanf("%d%d%d", &e1[i].u, &e1[i].v, &e1[i].wi);
}
}
void solve() {
MST();
for (int i=1;i<=n;i++) if (!dep[i]) dfs1(i, 0);
for (int i=1;i<=n;i++) if (!p[i]) dfs2(i, i);
for (int i=1;i<=n;i++) if (fa[i]!=0) update(1,1,n,p[i],dwi[i]);
scanf("%d", &Q);
for (int i=1;i<=Q;i++) {
int u, v;
scanf("%d%d", &u, &v);
int a1 = find(u), b1 = find(v);
if (a1!=b1) {printf("-1\n"); continue;}
printf("%d\n", findMax(u, v));
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d%d", &n, &m)==2) init(), solve();
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
77
78
79
80
81
82
83
84
85
86
87
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 10000 + 5, MAXM = 50000 + 5, INF = 1000000000;
struct data1 {
int u, v, wi;
bool operator < (const data1 &x) const {
return wi > x.wi;
}
}e1[MAXM];//原图
struct data2 {
int v, wi;
}e2[MAXM*2];//最大树
vector<int> G[MAXN];//最大树
int dwi[MAXN], en, n, m, dep[MAXN], fa[MAXN], f[MAXN];
void dfs(int u, int pa) {
dep[u] = dep[pa] + 1, fa[u] = pa;
for (int i=0;i<G[u].size();i++) {
data2 d2 = e2[G[u][i]];
int v = d2.v;
if (v!=fa[u]) {
dfs(v, u);
dwi[v] = d2.wi;
}
}
}
int find(int x) {return x==f[x] ? x : f[x] = find(f[x]);}//并查集find
void MST() {//Kruskal
sort(e1+1, e1+1+m);
for (int i=1;i<=m;i++) {
int a1 = find(e1[i].u), b1 = find(e1[i].v);
if (a1==b1) continue;
f[a1] = b1;
en++, e2[en].v = e1[i].v, e2[en].wi = e1[i].wi, G[e1[i].u].push_back(en);
en++, e2[en].v = e1[i].u, e2[en].wi = e1[i].wi, G[e1[i].v].push_back(en);
}
}
int findMax(int u, int v) {
int ret = INF;
if (dep[u]<dep[v]) swap(u, v);
while (dep[u]>dep[v]) ret = min(ret, dwi[u]), u = fa[u];
if (u==v) return ret;
while (u!=v) ret = min(ret, min(dwi[v], dwi[u])), u = fa[u], v = fa[v];
return ret;
}
void clean() {
en = 0;
for (int i=0;i<=n;i++) {
dep[i] = fa[i] = 0;
f[i] = i;
G[i].clear();
}
}
void init() {
clean();
for (int i=1;i<=m;i++) {
scanf("%d%d%d", &e1[i].u, &e1[i].v, &e1[i].wi);
}
}
void solve() {
MST();
for (int i=1;i<=n;i++) if (!dep[i]) dfs(i, 0);
int Q;
scanf("%d", &Q);
for (int i=1;i<=Q;i++) {
int u, v;
scanf("%d%d", &u ,&v);
int a1 = find(u), b1 = find(v);
if (a1!=b1) {printf("-1\n"); continue;}
printf("%d\n", findMax(u, v));
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("2.out", "w", stdout);
#endif
while (scanf("%d%d", &n, &m)==2) init(), solve();
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
#include<cstdio>
#include<algorithm>
#include<windows.h>
#include<winbase.h>
#include<set>
using namespace std;
int n = 3, m = 5, w = 5, q = 3;
int main() {
freopen("1.in", "w", stdout);
srand(GetTickCount());
printf("%d %d\n", n, m);
for (int i=1;i<=m;i++) {
int a = rand()%n+1;
int b = rand()%n+1;
while (a==b) b = rand()%n+1;
printf("%d %d %d\n", a, b, rand()%w);
}
printf("%d\n", q);
for (int i=1;i<=q;i++) {
int a = rand()%n+1;
int b = rand()%n+1;
while (a==b) b = rand()%n+1;
printf("%d %d\n", a, b);
}
return 0;
}

------ 本文结束 ------