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

Alex_Wei · 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