Loading...

洛谷 P1967 货车运输

check评论:0 条 remove_red_eye浏览量:309 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-05-19

此题略水
简单说下思路:以1为根先构建一颗最大生成树,然后对于每次查询,求出其LCA即可
code:

#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
#define N 100010
#define INF 0x3f3f3f3f
using namespace std;
int n,m,q,x,y,cnt;
int head[N],nxt[N*2],to[N*2],w[N*2],p[N*5],f[N][20],minv[N][20],dep[N];
struct Edge
{
    int x,y,z;
    bool operator<(const Edge& rhs)const 
    {
        return z>rhs.z;
    }
}e[N*5];

void Add(int x,int y,int z)
{
    to[cnt]=y;
    w[cnt]=z;
    nxt[cnt]=head[x];
    head[x]=cnt++;
}
inline int find(int x)
{
    if(p[x]==x)
    {
        return x;
    }
    return p[x]=find(p[x]);
}
inline void kruskal()
{
    for(int i=0;i<m;i++) 
    {
        p[i]=i;    
    }
    sort(e,e+m);
    for(int i=0;i<m;i++)
    {
        if(find(e[i].x)!=find(e[i].y))
        {
            Add(e[i].x,e[i].y,e[i].z);
            Add(e[i].y,e[i].x,e[i].z);
            p[find(e[i].x)]=find(e[i].y);
        }
    }     
}
void DFS(int x, int p)
{
    for(int i=head[x];~i;i=nxt[i])
    {
        if(i != p)
        {
            dep[to[i]]=dep[x] + 1;
            f[to[i]][0]=x;
            minv[to[i]][0]=w[i];
            DFS(to[i],i^1);
        }
    }    
}
int lca(int x,int y)
{
    int ans=INF;
    if(dep[x]>dep[y]) 
    {
        swap(x, y);
    }
    for(int i=15;i>=0;i--) 
    {
        if(dep[f[y][i]]>=dep[x])
        {
            ans=min(ans,minv[y][i]);
            y=f[y][i];
        }
    }
    if(x==y) 
    {
        return ans; 
    } 
    for(int i=15;i>=0;i--) 
    {  
        if(f[x][i]!=f[y][i]) 
        {
            ans=min(ans,min(minv[x][i],minv[y][i])); 
            x=f[x][i];  
            y=f[y][i];  
        }
    }  
    return f[x][0]==0?-1:min(ans,min(minv[x][0],minv[y][0]));
}
int main()
{
    freopen("netcs.in","r",stdin);
    freopen("netcs.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
    }
    memset(head,-1,sizeof(head));
    kruskal();
    dep[1]=1;
    DFS(1,-1);
    for(int j=1;j<=15;j++) 
    {
        for(int i=1;i<=n;i++)
        {
            f[i][j]=f[f[i][j-1]][j-1];
            minv[i][j]=min(minv[i][j-1], minv[f[i][j-1]][j-1]);
        }
    }  
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
    return 0;
}

chevron_left 洛谷P4388 矩形
NOIP2017 宝藏 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名