[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 H: qwb与学姐 [MST+LCA]【数据结构】

2017-06-03 02:36:00 Tabris_ 阅读数:735


博客爬取于2020-06-14 22:40:15
以下为正文

版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72849743


题目链接:http://115.231.222.240:8081/JudgeOnline/problem.php?cid=1005&pid=7
——————————————————————————————————————————
Problem H: qwb与学姐
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 113 Solved: 44
[Submit][Status][Web Board]
Description
qwb打算向学姐表白,可是学姐已经受够了他的骚扰,于是出了一个题想难住他:
已知一幅n个点m条边的无向图,定义路径的值为这条路径上最短的边的长度,
现在有 k个询问,
询问从A点到B点的所有路径的值的最大值。
qwb听完这个问题很绝望啊,聪明的你能帮帮他吗?
Input
一组数据。
第一行三个整数n,m,k (1<=N<=50000,m<=200000,k<=100000)。
第2…m+1行:三个正整数:X, Y, and D (1 <= X <=N; 1 <= Y <= N,1<=D<=215) 表示X与Y之间有一条长度为D的边。
第m+2…m+k+1行: 每行两个整数A B(1<=A,B<=n且A≠B),意义如题目描述。
保证图连通。
Output
对于每个询问输出一行,一共k行,每行输出A点到B点的所有路径的值的最大值。
Sample Input
4 5 3
1 2 6
1 3 8
2 3 4
2 4 5
3 4 7
2 3
1 4
3 4
Sample Output
6
7
7
——————————————————————————————————————————

他要找所有路径的最大值,那么我只需要留校路径最大的那个就好了

这里有一个贪心策略,就是最大生成树,
这样能保证,两点间在图上其他的路径的值都小于最大生成树的

然后问题就是如何求两点间路径最小值了

最开始写了个树剖,发现由于是边权在维护的时候lca位置不好维护
于是GG,在提示下学习了倍增求lca

知识点不介绍了,

因为同样是变成了点权
我们只需要求路径最小的时候变成两个路径的最小值,非别是(u,x(fa[x]=lca)),(v,y(fa[y]=lca))

这样下来就好办多了,找到lca之后维护最小值就好了

附本题代码
——————————————————————————————————————————

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
# include<bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N = 50000+7;
const int MOD = 1e9+7;
const int INF = (~(1<<31));
const double Pi = acos(-1.0);

int read(){
int x=0,f=1;char ch= getchar();
while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
/*****************************/
int n,m,k;
vector<pair<int,int> >G[N];
void add(int u,int v,int w){
G[u].push_back(make_pair(v,w));
G[v].push_back(make_pair(u,w));
}
struct node {
int u,v,w;
}e[N*4];
bool cmp(node a,node b){
return a.w>b.w;
}
/*****************************/
int pre[N];
int findi(int x){
int r=x;
while(r!=pre[r])r=pre[r];
int i=x,j;
while(i!=r){
j=pre[i];
pre[i]=r;
i=j;
}
return r;
}
void join(int x,int y){
int fx=findi(x),fy=findi(y);
pre[fx]=fy;
}
void MST(){
for(int i=1,sum=0;i<=m&&sum<n-1;i++){
if(findi(e[i].u)==findi(e[i].v)) continue;
join(e[i].u,e[i].v);
add(e[i].u,e[i].v,e[i].w);
sum++;
}
}
/*****************************/
int fa[N][20],dep[N],mi[N][20];
void dfs(int u,int f,int d){
fa[u][0]=f;dep[u]=d;
for(int i=1;i<20;i++)
fa[u][i]=fa[fa[u][i-1]][i-1],mi[u][i]=min(mi[u][i-1],mi[fa[u][i-1]][i-1]);
int gz=G[u].size();
for(int i=0,to;i<gz;i++){
to=G[u][i].first;
if(to==f)continue;
mi[to][0]=G[u][i].second;
dfs(to,u,d+1);
}
}
void solve(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
int lca=-1,tu=u,tv=v;

for(int i=19;i>=0;i--)
if(dep[fa[u][i]]>=dep[v])
u=fa[u][i];

if(u==v) lca=v;// return v;
else{
for(int i=19;i>=0;i--){
if(fa[u][i]==fa[v][i]) continue;
u=fa[u][i];
v=fa[v][i];
}
lca = fa[v][0];//return fa[v][0];
}
// cout<<lca<<" ";
int miu=INF,miv=INF;
for(int i=19;i>=0;i--){
if(dep[fa[tu][i]]>=dep[lca])
miu=min(miu,mi[tu][i]),tu=fa[tu][i];
if(dep[fa[tv][i]]>=dep[lca])
miv=min(miv,mi[tv][i]),tv=fa[tv][i];
}
//miu=min(miu,mi[tu][0]),miv=min(miv,mi[tv][0]);
printf("%d\n",min(miu,miv));
}
/*****************************/
void init(){
for(int i=1;i<=n;i++) pre[i]=i;
memset(mi,0x7f,sizeof(mi));
}

int main(){
while(~scanf("%d%d%d",&n,&m,&k)){
init();
for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
sort(e+1,e+m+1,cmp);
MST();
dfs(1,0,1);
// for(int i=1;i<=n;i++){
// printf("%d: ",i);
// for(int j=0;j<20;j++)
// printf("%d ",mi[i][j]);
// puts("");
// }
for(int u,v;k--;){
scanf("%d%d",&u,&v);
solve(u,v);
}
}
return 0;
}