Tarjan（lca）

http://codevs.cn/problem/2370

/

2370 小机房的树

时间限制: 1 s

空间限制: 256000 KB

题目等级 : 钻石 Diamond

题目描述 Description

小机房有棵焕狗种的树，树上有N个节点，节点标号为0到N-1，有两只虫子名叫飘狗和大吉狗，分居在两个不同的节点上。有一天，他们想爬到一个节点上去搞基，但是作为两只虫子，他们不想花费太多精力。已知从某个节点爬到其父亲节点要花费 c 的能量（从父亲节点爬到此节点也相同），他们想找出一条花费精力最短的路，以使得搞基的时候精力旺盛，他们找到你要你设计一个程序来找到这条路，要求你告诉他们最少需要花费多少精力

输入描述 Input Description

第一行一个n，接下来n-1行每一行有三个整数u，v, c 。表示节点 u 爬到节点 v 需要花费 c 的精力。
第n+1行有一个整数m表示有m次询问。接下来m行每一行有两个整数 u ，v 表示两只虫子所在的节点

输出描述 Output Description

一共有m行，每一行一个整数，表示对于该次询问所得出的最短距离。

样例输入 Sample Input

1 0 1

2 0 1

1 0

2 0

1 2

样例输出 Sample Output

数据范围及提示 Data Size & Hint

1<=n<=50000， 1<=m<=75000， 0<=c<=1000

思路：建图有点蒙就是。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <iostream>

#include <algorithm>

#include <iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include <stdio.h>

#include <string.h>

#include <vector>

#define ME(x , y) memset(x , y , sizeof(x))

#define SF(n) scanf("%d" , &n)

#define rep(i , n) for(int i = 0 ; i < n ; i ++)

#define INF  0x3f3f3f3f

using namespace std;

const int N = 5e4 +  ;

const int M = 8e4 +  ;

int head[N] , tol , qhead[N] , qtol ;

int dis[N] , pre[N] , vis[N] , ans[M];

int n ;

struct Grafe//建图结构体

{

    int from , to , w , next;

}path[N << ];

struct node//询问两点最近祖先结构体

{

    int to , id , next ;

}query[M << ];

void add(int u , int v , int w)//建图

{

    path[tol] = {u , v , w , head[u]};

    head[u] = tol++;

}

void qadd(int u , int v , int id)//加入询问的两点

{

    query[qtol] = {v , id , qhead[u]};

    qhead[u] = qtol++;

}

int get(int x)//查

{

    return x == pre[x] ? x : get(pre[x]);

}

void lca(int u)//dfs 根节点

{

    vis[u] =  ;//标记遍历过的点

    for(int i = head[u] ; i != - ; i = path[i].next)//遍历所有点

    {

        int v = path[i].to;

        if(vis[v]) continue ;

        dis[v] = dis[u] + path[i].w ;

        lca(v);

        pre[v] = u ;//并

    }

    for(int i = qhead[u] ; i != - ; i = query[i].next) //同时询问所有点

    {

        int v = query[i].to;

        if(vis[v])//是关联点之前是否出现过

        {

            int fa = get(v);//最近共同祖先

            ans[query[i].id] = dis[u] + dis[v] - (dis[fa] << );

        }

    }

}

void init()

{

    memset(head , - , sizeof(head));

    memset(qhead , - , sizeof(qhead));

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

        pre[i] = i ;

}

int main()

{

    scanf("%d" , &n);

    init();

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

    {

        int u , v , w ;

        scanf("%d%d%d" , &u , &v , &w);

        add(u , v , w);//有权双向图

        add(v , u , w);

    }

    int q ;

    scanf("%d" , &q);

    for(int i = ; i <= q ; i++)

    {

        int u , v ;

        scanf("%d%d" , &u , &v);

        qadd(u , v , i);//双向

        qadd(v , u , i);

    }

    lca();

    for(int i =  ; i <= q ; i++)

    {

        printf("%d\n" , ans[i]);

    }

    return  ;

}

巴特西

Tarjan（lca）

http://codevs.cn/problem/2370

/

2370 小机房的树

最新文章

热门文章