NOIP 2013 货车运输

洛谷 P1967

https://www.luogu.org/problemnew/show/P1967

JDOJ 2228

https://neooj.com/oldoj/problem.php?id=2228

题目描述

输入输出格式

输入格式：

第一行有两个用一个空格隔开的整数

接下来

接下来一行有一个整数 q，表示有 q 辆货车需要运货。

接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意：x 不等于 y 。

输出格式：

输入输出样例

输入样例#1：复制

输出样例#1：复制

3
-1
3

说明

对于 $30\%30%的数据，0 < n < 1,000,0 < m < 10,000,0 < q< 1,0000<n<1,000,0<m<10,000,0<q<1,000；$

对于 $60\%60%的数据，0 < n < 1,000,0 < m < 50,000,0 < q< 1,0000<n<1,000,0<m<50,000,0<q<1,000；$

对于 $100\%100%的数据，0 < n < 10,000,0 < m < 50,000,0 < q< 30,000,0 ≤ z ≤ 100,0000<n<10,000,0<m<50,000,0<q<30,000,0≤z≤100,000。$

$这道题其实比较复杂，但是题面比较简单，大家千万不要被迷惑掉，以为这道题就是单纯的最长路，但是其实这道题考的是LCA$

$为什么是LCA呢？$

$首先，两点间的最长距离一定存在于图的最大生成树上，而我们要求两点间最长路的最小值，但是两个节点想要互相到达，一定要通过他们共同的祖先，针对于这道题，就是要求被询问两点的最近公共祖先。$

$首先LCA是基于有根树上的概念，所以我们首先想到的应该是初始图的最大生成树，个人不推荐使用prim算法，不太好写，kruskal算法是较优选择，我们可以通过写kruskal求出原图最大生成树，然后再次存储其最大生成树，在树上跑LCA,期间维护两点之间的路径，最后就可以出解。$

#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 999999999
using namespace std;
int n,m,q,tot,cnt;
int fa[10001],head[10001],f[10001][21],w[10001][21],v[10001],deep[10001];
struct node
{
    int x,y,z;
}e[100001];
struct tree
{
    int to,nxt,val;
}t[100001];
bool cmp(node a,node b)
{
    return a.z>b.z;
}
int find(int x)
{
    if(fa[x]==x)
        return x;
    return fa[x]=find(fa[x]);
}
void add(int x,int y,int z)
{
    t[++tot].to=y;
    t[tot].val=z;
    t[tot].nxt=head[x];
    head[x]=tot;
}
void dfs(int x)
{
    v[x]=1;
    for(int i=head[x];i;i=t[i].nxt)
    {
        int y=t[i].to;
        if(v[y]==1)
            continue;
        deep[y]=deep[x]+1;
        f[y][0]=x;
        w[y][0]=t[i].val;
        dfs(y);
    }
}
int lca(int x,int y)
{
    if(find(x)!=find(y))
        return -1;
    int ans=INF;
    if(deep[x]>deep[y])
        swap(x,y);
    for(int i=20;i>=0;i--)
        if(deep[f[y][i]]>=deep[x])
        {
            ans=min(ans,w[y][i]);
            y=f[y][i];
        }
    if(x==y)
        return ans;
    for(int i=20;i>=0;i--)
        if(f[x][i]!=f[y][i])
        {
            ans=min(ans,min(w[x][i],w[y][i]));
            x=f[x][i];
            y=f[y][i];
        }
    return ans=min(ans,min(w[x][0],w[y][0]));
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        e[i].x=x;
        e[i].y=y;
        e[i].z=z;
    }
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int fx=find(e[i].x);
        int fy=find(e[i].y);
        if(fx!=fy)
        {
            add(e[i].x,e[i].y,e[i].z);
            add(e[i].y,e[i].x,e[i].z);
            fa[fx]=fy;
        }
    }
    for(int i=1;i<=n;i++)
        if(v[i]==0)
        {
            deep[i]=1;
            dfs(i);
        }
    for(int i=1;i<=20;i++)
        for(int j=1;j<=n;j++)
        {
            f[j][i]=f[f[j][i-1]][i-1];
            w[j][i]=min(w[j][i-1],w[f[j][i-1]][i-1]);
        }
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d
",lca(x,y));
    }
    return 0;
}

先上代码。

这里还有一个知识点，是倍增法求LCA的方式。

求LCA有三种方式，朴素算法（也叫爬一爬），倍增优化版算法（朴素的优化，使用并查集维护），还有离线TARJAN算法。这几种算法我也不敢说完全能写对（逃，这道题也出现了很多细节上和理解上的失误，希望大家能够借鉴改正。

deep[i]表示i节点的深度，f[i][j]表示节点i的2的j次方辈的祖先，那么根据这个定义，我们可以推出一个式子：f[i][j]=f[f[i][j-1]][j-1];

请自行画图理解。

然后我们预处理求出每个节点的2的k次方辈的祖先。然后就可以在LCA函数里由原先的爬一爬，一步一步走变成一次走好多步，其实原理没有变，所以只是说它是朴素算法的一个优化。

这里有一个问题，f数组的第二维要开多大？这个涉及到对数运算，初三表示不会（逃

不过我知道需要自己写程序输出一下(int)(log(n))/log(2);

原理不会

然后我们需要在深搜（预处理）完毕之后才能初始化f数组

然后附上一份裸的倍增LCA模板，一些细节问题已经在代码中标志。

int lca(int x,int y)
{
    int re;
    if(deep[x]<deep[y]) swap(x,y);    //常规处理
    for(int i=16;i>=0;i--)        //从大到小处理
        if( deep[ fa[x][i] ] >= deep[y] )
            x=fa[x][i];
    if(x==y)  return x;    //这句话是不能省的，否则返回的re是没有值的。
    for(int i=16;i>=0;i--)
        if(fa[x][i]!=fa[y][i])    x=fa[x][i],y=fa[y][i];
        else re=fa[x][i];
    return re;
}

报告完毕。