洛谷 P1967 NOIP2013提高组 货车运输 题解【倍增】【LCA】

作者: wjyyy 分类: LCA,倍增,,生成树,解题报告,贪心 发布时间: 2018-06-24 20:38

点击量:12

 

   求使图上两点间最小边权最大的题目(*////▽////*)。。。

 

题目描述

A国有n座城市,编号从1到n,城市之间有m条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有q辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。

 

输入输出格式

输入格式:
第一行有两个用一个空格隔开的整数n,m,表示A国有n座城市和m条道路。

 

接下来m行每行3个整数x,y,z,每两个整数之间用一个空格隔开,表示从x号城市到y号城市有一条限重为z的道路。注意:x不等于y,两座城市之间可能有多条道路。

 

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

 

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

 

输出格式:
共有q行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。如果货车不能到达目的地,输出-1。

 

输入输出样例

输入样例#1:
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

 

输出样例#1:
3
-1
3

 

说明

对于30%的数据,0<n<1,000,0<m<10,000,0<q<1,000 ;

 

对于60%的数据,0<n<1,000,0<m<50,000,0<q<1,000 ;

 

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

 

解法:

 

   floyd都不一定拿得到30分,这个题是基于贪心的。

 

   假设图中只有一个联通块,那么任意两点间的最小边权的最大值一定是在它的最大生成树上。根据贪心我们可以知道,通过最大生成树,两点间互达,路径上的最小边权一定最大,用Kruskal算法可以形象地看出最大生成树在贪心上的作用。

 

   我们基于最大生成树,对一个联通块任意两个点求路径上最小边权,如果用dfs,时间复杂度是\(O(NQ)\),Q是询问次数。因此,看出来最大生成树的贪心,60分是很好拿的。(不同联通块之间的查询直接输出-1即可)

 

   有没有什么快一点的方法来求两点间路径上的信息呢?因为两点间的路径一定是最大生成树上的一条链,所以我们可以在树上做文章。我们给一棵树任取一个根,任意两点间就有了最近公共祖先。我们知道两点的路径一定经过最近公共祖先,所以我们思路就有了,我们先把图建成一棵最大生成树。

 

   对于每个询问(u,v),分别查询u,v到lca(u,v)路径上最小边权,并继续取最小值,就是一次询问。那么LCA可以由tarjan或倍增求,如果用tarjan,那么查找lca的时间是O(N),但寻找到lca路径上的信息就会变成\(O(N^2)\),这时我们应该选取倍增求,因为倍增过程可以查询并处理路径上的信息,而求lca和路径访问的时间复杂度稳定为\(O(N\log N)\),这个题就迎刃而解了(。・∀・)ノ。

 

   值得注意的是,倍增时开两个数组f[i][j],表示i节点的第\(2^j\)层祖先是谁,如果\(2^j>depth(i)\),所求值就是根节点,fm[i][j]中i,j与f数组同义。当我们求lca时,用一个ans存储最小值,并持续更新。而我们最后判断,首先要跳到同层,然后让2的指数递减,相当于一个二分的过程。不过有可能直接使x和y跳到同一点,例如x,y的最近公共祖先就是x或y的情况,或者x,y到达一层后,离最近公共祖先刚好是2的整数次幂(这种情况在下面的标程中不会出现),因为判断条件是x,y最终的父亲刚好为最近公共祖先,因此还要更新一层。为防止这种情况出现,我们只要特判x是否等于y,再看需不需要加就可以了。

 

Code:

#include<cstdio>
#include<algorithm>
int min(int x,int y)
{
    return x<y?x:y;
}
struct edge
{
    int x,y,v;
    edge(int x,int y,int v)
    {
        this->x=x;
        this->y=y;
        this->v=v;
    }
    edge(){}
    friend bool operator <(edge a,edge b)
    {
        return a.v>b.v;//最大生成树
    }
}e[51000],tree[51000];
int cnt=0;
int s[10100];
int my_find(int x)
{
    if(s[x]==x)
        return x;
    return s[x]=my_find(s[x]);
}
void my_union(int x,int y)
{
    s[my_find(y)]=my_find(x);
}
struct node
{
    int n,v;
    node *nxt;
    node(int n,int v)
    {
        this->n=n;
        this->v=v;
        nxt=NULL;
    }
    node()
    {
        nxt=NULL;
    }
};
node head[10100],*tail[10100];
int f[10100][22],fm[10100][22];
int dpt[10100];
void dfs(int x)
{
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(!dpt[p->n])
        {
            dpt[p->n]=dpt[x]+1;
            f[p->n][0]=x;
            fm[p->n][0]=p->v;
            dfs(p->n);
        }
    }
}
int main()
{
    int n,m,u,v,w;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        tail[i]=&head[i];
        s[i]=i;
    }

    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        e[i]=edge(u,v,w);
    }
    std::sort(e+1,e+m+1);
    for(int i=1;i<=m;i++)
        if(my_find(e[i].x)!=my_find(e[i].y))
        {
            tree[++cnt]=e[i];
            my_union(e[i].x,e[i].y);
        }
    for(int i=1;i<=cnt;i++)
    {
        u=tree[i].x;
        v=tree[i].y;
        w=tree[i].v;
        tail[u]->nxt=new node(v,w);
        tail[u]=tail[u]->nxt;
        tail[v]->nxt=new node(u,w);
        tail[v]=tail[v]->nxt;
    }
    for(int i=1;i<=n;i++)
    {
        s[i]=my_find(i);//顺便整理状态
        if(!dpt[i])
        {
            f[i][0]=i;
            fm[i][0]=0x3fffffff;
            dpt[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];
            fm[j][i]=min(fm[j][i-1],fm[f[j][i-1]][i-1]);
        }
    int q;
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%d",&u,&v);
        if(s[u]!=s[v])
        {
            printf("-1\n");
            continue;
        }
        if(dpt[u]<dpt[v])
        {
            int t=u;
            u=v;
            v=t;
        }
        int ans=99999999;
        for(int i=20;i>=0;i--)
            if(dpt[u]-(1<<i)>=dpt[v])
            {
                ans=min(ans,fm[u][i]);
                u=f[u][i];
            }
        for(int i=20;i>=0;i--)
            if(f[u][i]!=f[v][i])
            {
                ans=min(ans,fm[u][i]);
                ans=min(ans,fm[v][i]);
                u=f[u][i];
                v=f[v][i];
            }
        if(u!=v)
        {
            ans=min(ans,fm[u][0]);
            ans=min(ans,fm[v][0]);
        }
        
        printf("%d\n",ans);
    }
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
更多阅读
/* */