自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 21:43:51，当前版本为作者最后更新于2019-02-09 16:53:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解 P2959 【[USACO09OCT]悠闲漫步The Leisurely Stroll】

一道对DFS新手比较友好的题目

题目其实就是问Bessie最多能走过多少分岔节点

思路：DFS（BFS也可以），边搜索边更新答案

具体思路见~~（一份对DFS新手比较友好的）~~代码：

#include<bits/stdc++.h>//万能头
using namespace std;
int p,a[1010],b[1010],c,n;//a[x],b[x]是分岔节点x通向的两块区域，n是答案 
void dfs(int m,int s)//到达分岔节点m，共走过了s个分岔节点
{
	if(a[m]!=0)dfs(a[m],s+1);//如果不是牧场就前往这个分岔节点
	if(b[m]!=0)dfs(b[m],s+1);//同上
	n=max(n,s);//更新答案
}
int main()
{
	cin>>p;
	for(int x=1;x<p;x++)cin>>c,cin>>a[c]>>b[c];//输入 
	dfs(1,1),cout<<n;//输出 
	return 0;
}

如果有错误欢迎在右侧——>评论区指正

求赞QWQ