题解 | TheLeisurelyStroll-牛客假日团队
The Leisurely Stroll
https://ac.nowcoder.com/acm/contest/1082/G
题目描述
Bessie looks out the barn door at the beautiful spring day and thinks to herself, 'I'd really like to enjoy my walk out to the pastures for the tender spring grass.' She knows that once she leaves the barn, she will traverse a path for a while, take one of two choices that lead to other paths, follow one of them, take one of two other choices, and continue on until the path leads to a verdant pasture.
She decides to make the set of path choices that enables her to walk over the greatest number of cow paths on her way to breakfast. Given the description of these paths, determine how many cow paths she traverses, presuming that she commences choosing various paths as soon as she leaves the barn.
Consider this set of paths (lines), pastures ('%'), and the highlighted ('#') route to a pasture on the right:
The pasture reached from choice-node 9 is one of two that enable Bessie to traverse seven different cowpaths on the way to breakfast. These are the 'furthest' pastures from node 1, the barn.Three integers describe each node: Cn, D1, and D2. Cn is the nodenumber (1 <= Cn <= P-1); D1 and D2 are the destinations from that node (0 <= D1 <= P-1; 0 <= D2 <= P-1). If D1 is 0, the node leads to a pasture in that direction; D2 has the same property.
输入描述:
* Line 1: A single integer: P
* Lines 2..P: Line i+1 contains three space-separated integeres that describe a choice-node: Cn, D1, and D2
输出描述:
* Line 1: A single integer that is the largest number of paths Bessie can traverse on the way to the furthest pasture.
示例1
10
7 8 0
5 0 6
9 0 0
6 0 7
3 4 0
2 5 0
8 0 9
4 0 0
1 2 3
7
This input describes the example farm layout in the task description.
1-2-5-6-7-8-9-P is one of the longest routes.
解答
不得不说这道题的图有点吓人，但实际上很多都没有用
通过题上说的“三岔路口”（对于每一个节点有三条连接，其中一条连接父节点，另外两条连接子节点）和数据，可以那些乱七八糟的路和牧场看成是一棵二叉树，又因为 “对任意一个节点来说，只有一条从节点1开始的路径可以到达” ，所以可以把1作为根节点。从而将题目转化为求一棵以1为节点的二叉树的深度。
核心算法：DFS
注意：
1.根节点的深度在此题中应该为1（节点1的实际意义是一个要算入答案的一个牧场）
2.有n个节点，他们之间的连接数应该为n-1
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<cmath>
typedef long long ll;
using namespace std;
struct Node{
int id,l,r;
Node(){
l=r=0;
}
}tr[1010];//保存二叉树
int p,dep[1010],ans=0;//个数，节点深度，答案（树的深度）
void addedge(int i,int r,int l){
tr[i].id=i;
tr[i].l=l;
tr[i].r=r;
}//编号为i的接点的左节点l，右节点r
void Init() {
scanf("%d",&p);
int a,b,c;
for(int i=1;i<p;i++){
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);
}
dep[1]=1;//注意初始化
}
void DFS(int i){
if(tr[i].l){//如果左节点不为0
dep[tr[i].l]=dep[i]+1;//左节点的深度
ans=max(ans,dep[i]+1);//更新树的深度
DFS(tr[i].l);//接着左节点向下找
}
if(tr[i].r){//同理
dep[tr[i].r]=dep[i]+1;
ans=max(ans,dep[i]+1);
DFS(tr[i].r);
}
}
int main() {
Init();
DFS(1);
printf("%d",ans);
return 0;
} 
投递OPPO等公司7个岗位
