[NOIP2013]货车运输,最大生成树+LCA

Posted by Cww97 on 2016-08-20

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/52258432
codevs3287
之前写过一个pascal版本的,年代有点久远了

既然问最大的运货重量,那么每次都选众多路径中最大的边都显然是对的
那么把原本的图变成一颗最大生成树,选权值最大的n-treenum条边(treenum是联通块数量)
好吧,其实是个森林,
那么现在就变成了求树上简单路径上的最值
树上简单路径,,LCA咯,
同时可以像维护st表一样维护一个树上的RMQ
当然这里不能像st表一样暴力重叠,不能重叠,看看lca的套路,咱们二进制拆分吧
fa[x][i]:x节点向上2的i次方的祖先
di[x][i]:从x节点走到fa[x][i]的最大权值

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
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int N = 1e5 + 5;
int n,m;

struct gragh{
struct Edge{
int from,to,w;
Edge(){}
Edge(int x,int y,int z):from(x),to(y),w(z){}
bool operator < (const Edge& a)const{
return w < a.w;
}
}edges[N],be[N];
int E,f[N],fa[N][20],di[N][20],dep[N];
bool vis[N];
vector<int >G[N];
int F(int x){//并查集
return f[x]==x?x:(f[x]=F(f[x]));
}

inline void link(int x,int y,int z){
edges[++E]=Edge(x,y,z);
G[x].push_back(E);
}

void build(){
E=0;
for (int i=1;i<=n;i++)G[i].clear();
int x,y,z;
for (int i=1;i<=n;i++)f[i]=i;
for (int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
be[i]=Edge(x,y,z);
f[F(x)]=F(y);
}
}

void kruskal(){
int treenum = 0;//forests
memset(vis,0,sizeof(vis));
for (int i=1;i<=n;i++)if (!vis[F(i)]){
treenum++;vis[F(i)]=1;
}
for (int i=1;i<=n;i++)f[i]=i;
sort(be+1,be+m+1);
int cnt = 0;
for (int i=m;i>=1;i--){
int x = be[i].from;
int y = be[i].to ;
if (F(x)==F(y))continue;
f[F(x)]=F(y);
cnt++;
link(x,y,be[i].w);
link(y,x,be[i].w);
if (cnt==n-treenum)break;
}
}

void dfs(int x){
vis[x] = 1;
for (int i=1;i<=17;i++){
if(dep[x]<(1<<i))break;
fa[x][i]=fa[fa[x][i-1]][i-1];
di[x][i]=min(di[x][i-1],di[fa[x][i-1]][i-1]);
}
for (int i=0;i<G[x].size();i++){
Edge e = edges[G[x][i]];
if (vis[e.to])continue;
fa[e.to][0] = x;
di[e.to][0] = e.w;
dep[e.to] = dep[x]+1;
dfs(e.to);
}
}

int lca(int x,int y){
if (dep[x]<dep[y])swap(x,y);
int t = dep[x] - dep[y];
for (int i=0;i<=17;i++)
if ((1<<i)&t) x = fa[x][i];
for (int i=17;i>=0;i--)
if (fa[x][i]!=fa[y][i]){
x=fa[x][i];y=fa[y][i];
}
if (x==y)return x;
return fa[x][0];
}

int ask(int x,int f){//f:father
int ans = INF;
int t = dep[x]-dep[f];
for (int i=0;i<=17;i++)if(t&(1<<i)){
ans=min(ans,di[x][i]);
x = fa[x][i];
}
return ans;
}

void work(){
build();
kruskal();
memset(vis,0,sizeof(vis));
for (int i=1;i<=n;i++)if(!vis[i])dfs(i);
int q,x,y;
scanf("%d",&q);
while (q--){
scanf("%d%d",&x,&y);
if (F(x)!=F(y))puts("-1");
else {
int t = lca(x,y);
x = ask(x,t);
y = ask(y,t);
printf("%d\n",min(x,y));
}
}
}
}g;

int main(){
//freopen("truck.in","r",stdin);
//freopen("truck.out","w",stdout);
for (;~scanf("%d%d",&n,&m);)g.work();
return 0;
}

长代码写的要仔细一点