[原创]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;
}