Nowcoder girl 2019:第二题 吃桃
吃桃
https://ac.nowcoder.com/acm/contest/3405/B
题目链接🔗:吃桃
题意简述
这题要在有 个点的连通图中,以点 为起点,找到一条深度最深(长度最长)的路径,并且把路径记录下来。
解题思路
一共分为两步:
DP+DFS 找到每个点的所有子节点的最长深度,记录在 中, 为父节点的编号。
贪心递归 每次都选能走到最长深度的那个子节点。
注意点
-这个是无向图,如果a,b之间有边,要互存为父节点和子节点。为了防止遍历的时候走回来,记得开个 记录已经走过的点。【这题的OJ数据很弱,没有环。之前比赛时的代码没有记录每个节点是否走过,只在遍历的时候跳过父节点,也可以AK。但是在有环的情况下会死循环(吃掉的桃子又重新长出来了hhh,根据题意其实数据可以带环的,反正走过一遍之后桃子就被吃掉了,就得走别的有桃子的路径,没桃子就 路径结束)】
-图用数组模拟的链表存或者vector二维数组存都可以,都挺好写的,没啥区别(>-<定义变量的时候看起来整齐一点,我就用vector了)
代码
#include <iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 100010; bool st[N];//用来存这个节点有没有被走过 vector<int> a[N];//开一个二维数组来保存节点之间的连接 vector<int> w[N];//储存每个点出发的多种方案吃到的桃子数 vector<int> ans;//保存经过的节点 int dfs(int t) { st[t]=true; int mx = 0; for (auto it : a[t]) {//对于所有和t相接的点都继续遍历,得到它的深度 if (st[it] == true) {//跳过走过的点 w[t].push_back(-1); continue; } int v = dfs(it); st[it]=false; w[t].push_back(v);//把每个子节点的最大深度存下来 mx = max(mx, v);//选取最大的作为这个节点的深度备选 } return mx + 1;//这个就是该点的深度了 } void getans(int t) { ans.push_back(t);//先把选到的点t存到路径里 st[t]=true; int mxid = -1, mxval = -1;//用来记录下游节点里路径最长的点的编号和长度 for (int i = 0; i < a[t].size(); ++i) {//对于点t的每个下游节点,找到一个深度最大的点 int it = a[t][i]; if (st[it] == true) continue;//如果是走过的点就跳过 if (w[t][i] > mxval) { mxid = it; mxval = w[t][i]; } } if (mxid == -1) return;//没有下游节点的时候,我们就找完啦~ getans(mxid);//有下游节点时继续找下游节点的最长路径 st[mxid]=false; } int main() { int n, k;//节点数n,和起点k int ta, tb; cin >> n >> k; for (int i = 0; i < n - 1; ++i) { cin >> ta >> tb; a[ta].push_back(tb);//用a[i][?]来保存与第i个节点相邻的所有节点编号 a[tb].push_back(ta);//因为是无向图,双方互通 } dfs(k);//每个点的所有子节点的最长深度 getans(k);//得到最长路径的点编号,存在ans内 //依次输出ans容器中保存的路径 for (auto it : ans) cout << it << endl; return 0; }