欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

2020牛客暑期多校训练营(第九场) The Flee Plan of Groundhog

程序员文章站 2022-03-27 19:41:46
传送门.题意:有一棵树A 在点 1,B 在点 nA的移动速度是每秒走过一条边,B的移动速度是每秒走过两条边(也可以只走一条)前 t 秒 A 在不断的走向 B,B 不动,之后A还是逃,B开始追,问最迟什么时候追上思路:1、dfs找到t秒后A的位置node2、dfs1求出B到追到每个点的时间3、dfs2遍历A逃到每个点的时间,如果小于B追到的时间就继续逃,否则就更新ans代码#include #define inf 0x3f3f3f3f// #i...

传送门.

题意:有一棵树

A 在点 1,B 在点 n
A的移动速度是每秒走过一条边,B的移动速度是每秒走过两条边(也可以只走一条)
前 t 秒 A 在不断的走向 B,B 不动,之后A还是逃,B开始追,问最迟什么时候追上

思路:

1、dfs找到t秒后A的位置node
2、dfs1求出B到追到每个点的时间
3、dfs2遍历A逃到每个点的时间,如果小于B追到的时间就继续逃,否则就更新ans

代码
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
// #include <tr1/unordered_map>
#define ll long long
#define T int t;scanf("%d", &t);while(t--)
using namespace std;
// using namespace std::tr1;
const int mod = 1e9 + 7;
const int N = 1e7 + 10;
int n, t;
int node;	//t秒后A的位置
int cnt;
int head[N];
int t1[N];		//B追到的时间
int ans = 0;
struct ed{
    int to, ne;
}e[N<<4];
void add(int u, int v){
    e[cnt].to = v;
    e[cnt].ne = head[u];
    head[u] = cnt++;
}

int dfs(int u,int f,int step){	//找t秒后A的位置node
    if(u == n) return 1;	//如果这条路能到达B return 1
    for(int i = head[u]; i != -1; i = e[i].ne){
        int v = e[i].to;
        if(v==f) continue;
        int m = dfs(v,u,step+1);	
        if(step == t && m==1){	//如果第t秒所在位置是去往B的路上 更新值
            node = u;
        }
        if(m==1) return 1;	
    }
    return 0;
}
void dfs1(int u, int f,int step, int op){   //记录B追到每个点的时间
    t1[u] = step;	
    for(int i = head[u]; i != -1; i = e[i].ne){
        int v = e[i].to;
        if(v==f) continue;
        if(op)					//一秒可以跑两米
            dfs1(v,u,step+1,0);		
        else 
            dfs1(v,u,step,1);
    }
}
void dfs2(int u,int f, int step){		//搜索答案
    ans = max(ans,t1[u]);			
    for(int i = head[u]; i != -1; i = e[i].ne){
        int v = e[i].to;
        if(v==f) continue;
        if(step+1<t1[v]) dfs2(v,u,step+1);		//如果逃到v的时间小于追到的时间,继续逃,否则更新ans
        else ans = max(ans,t1[v]);
    }
}
int main(){
    int cnt = 0;
    memset(head,-1,sizeof(head));
    scanf("%d %d", &n, &t);
    for(int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        add(u,v);
        add(v,u);
    }
    dfs(1,-1,0);
    dfs1(n,-1,0,1);
    dfs2(node,-1,0);
    printf("%d\n", ans);

    return 0;
}
/*		测试样例
9 2
1 8
8 2
2 3
2 4
2 7
7 9
4 5
5 6
*/

本文地址:https://blog.csdn.net/HHeyanjie/article/details/107890336

相关标签: 题解