Luogu 2245 星际导航（最小生成树，最近公共祖先LCA，并查集）

2022-04-01 12:05:41

Luogu 2245 星际导航（最小生成树，最近公共祖先LCA，并查集）

Description

sideman做好了回到Gliese 星球的硬件准备，但是sideman的导航系统还没有完全设计好。为了方便起见，我们可以认为宇宙是一张有N 个顶点和M 条边的带权无向图，顶点表示各个星系，两个星系之间有边就表示两个星系之间可以直航，而边权则是航行的危险程度。

sideman 现在想把危险程度降到最小，具体地来说，就是对于若干个询问(A, B)，sideman 想知道从顶点A 航行到顶点B 所经过的最危险的边的危险程度值最小可能是多少。作为sideman 的同学，你们要帮助sideman 返回家园，兼享受安全美妙的宇宙航行。所以这个任务就交给你了。

对于40% 的数据，满足N≤1000，M≤3000，Q≤1000。

对于 80% 的数据，满足$$N≤104，M≤105，Q≤1000。$$

对于 100% 的数据，满足$$N≤105，M≤3×105，Q≤105，L≤109。$$数据不保证没有重边和自环。

Input

第一行包含两个正整数N 和M，表示点数和边数。

之后 M 行，每行三个整数A，B 和L，表示顶点A 和B 之间有一条边长为L 的边。顶点从1 开始标号。

下面一行包含一个正整数 Q，表示询问的数目。

之后 Q 行，每行两个整数A 和B，表示询问A 和B 之间最危险的边危险程度的可能最小值。

Output

对于每个询问， 在单独的一行内输出结果。如果两个顶点之间不可达， 输出impossible。

Sample Input

4 5

1 2 5

1 3 2

2 3 11

2 4 6

3 4 4

3

2 3

1 4

1 2

Sample Output

5

4

5

Http

Luogu:https://www.luogu.org/problem/show?pid=2245#sub

Source

最小生成树，最近公共祖先LCA，并查集

题目大意

在一张无向图上，求两点之间的一条路径使得路径上最大边权最小。

解决思路

笔者曾说过这种求最大值最小或最小值最大的问题多半是二分。

但这题不是的！

要解决这一题，首先要想明白的是为什么最后的解一定在该图的最小生成树上。（这个留给读者自己思考啦，虽然说确实看起来是的，但如何准确地证明呢？这是需要思考的）

然后我们就可以对要查询的两个点进行LCA啦。关于LCA的基本算法（倍增）请到我的这篇文章查看。

那么接下来的问题是，我们虽然求出了最近公共祖先，但我们并不知道这条路上的最大边权是多少啊？

这里我们引入一个新数组Path。Path[u][i]代表u到它的2^i祖先的路径上的最大边权。是不是觉得Path的定义与Parent有些相似呢？是的，这也是为了在倍增过程中方便地更新最后要求的值所定义的，并且它的求值与更新与Parent总是在一起的，过程也很类似，相信如果读者已经了解了LCA中Parent数组的求法，不难推导出Path的求法。

程序中要添加求Path数组的地方有两处

一是在dfs过程中，在得出Parent[v][0]的值得同时可以得出Path[v][0]=W[u][v]（W[u][v]代表u-v这条边上的权值）

二是在for循环求Parent[i][j]=Parent[Parent[i][j-1]][j-1]时，同样可以递推出Path[i][j]=max(Path[i][j-1],Path[Parent[i][j-1]][j-1])，即i到2j祖先路径上的最大值等于i到2(j-1)上的最大值和i的2(j-1)祖先到i的2(j-1)祖先的2^(j-1)祖先的最大值这两者中的最大值。（有点绕，多读几遍就好了）

最后，在进行倍增上翻的过程中，每次更新a与b的值的同时，记录下最大的路径就可以了。

如果还有不理解，请结合下面的代码分析。

PS:话说这题是不是和货车运输进行了**交易

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

class Edge1

{

public:

    int v,w;

};

class Edge2

{

public:

    int u,v,w;

};

bool operator < (Edge2 a,Edge2 b)

{

    return a.w<b.w;

}

const int maxN=100010;

const int maxM=300010;

const int inf=2147483647;

int n,m;

Edge2 E[maxM];

vector<Edge1> T[maxN];

//Union_Find_Set

int Mayuri[maxN];

//LCA

int Parent[maxN][25];

int Path[maxN][25];

int Depth[maxN];

bool vis[maxN];

int read();

void MST();

int Find(int u);

bool Union(int u,int v);

void LCA_init();

void dfs(int u);

int LCA(int a,int b);

int main()

{

    n=read();m=read();

    for (int i=1;i<=m;i++)

    {

        E[i].u=read();

        E[i].v=read();

        E[i].w=read();

    }

    MST();//求最小生成树

    LCA_init();//LCA的各种信息初始化

    int Q=read();

    for (int i=1;i<=Q;i++)

    {

        int x=LCA(read(),read());

        if (x==-1)

            cout<<"impossible"<<endl;//注意无解的情况，即这两点不连通，可以用并查集判断

        else

            cout<<x<<endl;

    }

    return 0;

}

int read()//读入优化

{

    int x=0;

    int k=1;

    char ch=getchar();

    while (((ch<'0')||(ch>'9'))&&(ch!='-'))

        ch=getchar();

    if (ch=='-')

    {

        k=-1;

        ch=getchar();

    }

    while ((ch>='0')&&(ch<='9'))

    {

        x=x*10+ch-48;

        ch=getchar();

    }

    return x*k;

}

void MST()//求最小生成树，这里用克鲁斯卡尔算法

{

    sort(&E[1],&E[m+1]);

    for (int i=1;i<=n;i++)//并查集初始化

        Mayuri[i]=i;

    int cnt=0;

    for (int i=1;i<=m;i++)

    {

        int u=E[i].u;

        int v=E[i].v;

        int w=E[i].w;

        if (Union(u,v))

        {

            T[u].push_back((Edge1){v,w});

            T[v].push_back((Edge1){u,w});

            cnt++;

            if (cnt==n-1)

                break;

        }

    }

    return;

}

int Find(int u)

{

    if (Mayuri[u]!=u)

        Mayuri[u]=Find(Mayuri[u]);

    return Mayuri[u];

}

bool Union(int u,int v)

{

    int fu=Find(u);

    int fv=Find(v);

    if (fu!=fv)

    {

        Mayuri[fu]=fv;

        return 1;

    }

    return 0;

}

void LCA_init()

{

    memset(Parent,0,sizeof(Parent));

    memset(Path,0,sizeof(Path));

    memset(Depth,0,sizeof(Depth));

    memset(vis,0,sizeof(vis));

    dfs(1);

    for (int j=1;j<=20;j++)

        for (int i=1;i<=n;i++)

        {

            Parent[i][j]=Parent[Parent[i][j-1]][j-1];

            Path[i][j]=max(Path[i][j-1],Path[Parent[i][j-1]][j-1]);//同时求解Path

        }

    return;

}

void dfs(int u)

{

    vis[u]=1;

    for (int i=0;i<T[u].size();i++)

    {

        int v=T[u][i].v;

        if (vis[v]==0)

        {

            Depth[v]=Depth[u]+1;

            Parent[v][0]=u;

            Path[v][0]=T[u][i].w;//记录Path的初值

            dfs(v);

        }

    }

}

int LCA(int a,int b)

{

    if (Find(a)!=Find(b))

    {

        return -1;

    }

    int max_path=0;

    if (Depth[a]<Depth[b])

        swap(a,b);

    for (int i=20;i>=0;i--)

        if ((Parent[a][i]!=0)&&(Depth[Parent[a][i]]>=Depth[b]))

        {

            max_path=max(max_path,Path[a][i]);//同时更新当前的最大边权

            a=Parent[a][i];

        }

    if (a==b)

        return max_path;

    for (int i=20;i>=0;i--)

        if ((Parent[a][i]!=0)&&(Parent[b][i]!=0)&&(Parent[a][i]!=Parent[b][i]))

        {

            max_path=max(max_path,Path[a][i]);//这里也是更新当前的最大边权

            max_path=max(max_path,Path[b][i]);

            a=Parent[a][i];

            b=Parent[b][i];

        }

    max_path=max(max_path,Path[a][0]);//最后要注意再与Path[a][0]和Path[b][0]比较一下，因为在原来的LCA中，公共祖先是Parent[a][0]或Parent[b][0]

    max_path=max(max_path,Path[b][0]);

    return max_path;

}
上一篇：VirtualBox安装Ubuntu16.04过程


下一篇：FireMonkey隐藏任务栏图标