[USACO 2009 Oct G]The Leisurely Stroll

Consider this set of paths (lines), pastures ('%'), and the highlighted ('#') route to a pasture on the right: % % / / 2----% 7----8----% 2----% 7####8----% / \ / \ # # # # 1 5----6 9----% 1 5####6 9----% \ \ \ \ \ \ \ # \ % % % \ % % % \ \ 3-----% 3-----% \ \ 4----% 4----% \ \ % % 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.

C++14(g++5.4) 解法, 执行用时: 6ms, 内存消耗: 496K, 提交时间: 2019-08-30 15:32:28

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int sum=0;
vector<int> v[1005];
void dfs(int x,int w){
	sum = max(sum,w);
	if(v[x].size()==0){
		return ;
	}
	for(int i=0;i<v[x].size();i++){
		dfs(v[x][i],w+1); 
	} 
}
int main(){
	cin >> n;
	int x,a,b;
	for(int i=1;i<n;i++){
		cin >> x >> a >> b;
		if(a)
		v[x].push_back(a);
		if(b)
		v[x].push_back(b);
	}	
	dfs(1,1);
	cout << sum <<endl;
}

Pascal(fpc 3.0.2) 解法, 执行用时: 3ms, 内存消耗: 256K, 提交时间: 2019-08-31 09:09:00

var
l,r:array[1..1000] of longint;
i,n,x,y,z:longint;

function aa(x:longint):longint;
var
ll,rr:longint;
begin
ll:=0;
rr:=0;
if l[x]>0 then ll:=aa(l[x]);
if r[x]>0 then rr:=aa(r[x]);
if ll>rr then exit(ll+1) else exit(rr+1);
end;

begin
read(n);
for i:=1 to n-1 do
 begin
  read(z,x,y);
  l[z]:=x;
  r[z]:=y;
 end;
writeln(aa(1));
end.

Python3(3.5.2) 解法, 执行用时: 34ms, 内存消耗: 4792K, 提交时间: 2019-08-30 17:28:57

# @Author:wxyww
import sys
sys.setrecursionlimit(1000000)
N = 30000
ls = [0 for i in range(0,N)]
rs = [0 for i in range(0,N)]

def dfs(x) :
	if(x == 0) :
		return 0
	return max(int(dfs(ls[x])),int(dfs(rs[x]))) + 1

n = int(input())
for i in range(1,n) :
	x,y,z = map(int,input().split())
	ls[x] = y
	rs[x] = z

print(dfs(1))

C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 456K, 提交时间: 2020-02-26 18:10:29

#include<bits/stdc++.h>
using namespace std;
int p,a[1010],b[1010],c,n;
void dfs(int m,int 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;
}

详情