SDNU__1015. 가장 먼 경로

1200 단어 SDNUOJ
n개의 노드가 있는 두 갈래 나무가 있는데, 그 노드의 번호는 1부터 n까지이고, 뿌리 노드의 번호는 1이며, 그 모서리마다 정해진 길이가 있다.이 두 갈래 나무 중 뿌리 노드에서 가장 먼 노드를 구해 주세요.
Input
첫 번째 줄: 하나의 숫자 n(1<=n<=100)은 이 두 갈래 나무 노드의 수량을 나타낸다.
2에서 n+1행: 줄마다 세 개의 정수(int를 초과하지 않음)가 있고, i행의 세 개의 정수는 각각 i-1의 노드와 부모 노드 사이의 길이, i-1의 노드 왼쪽 아이의 번호와 i-1의 노드 오른쪽 아이의 번호를 나타낸다.
Output
가장 먼 거리.
Sample Input

0 2 3
1 4 5
3 6 7
4 0 0
6 0 0
3 0 0
2 0 0
Sample Output 7
dfs
입력에 따라 두 갈래 트리를 정의한 다음 dfs로 검색하여 최대값을 저장합니다
#include
#include
#include
#include
using namespace std;
struct node{
	int sf;
	int lz;
	int rz;
}a[105];
int tree[105][2];
int gen;
int n;
int retmax = -99;
void dfs(int x,int mys)
{
	for(int j = 0;j < 2;j++)
	{
		if(tree[x][j] == 0)break; 
		dfs(tree[x][j],mys + a[tree[x][j]].sf);
	}
	if(mys > retmax)
	{
		retmax = mys;
	}
}
int main()
{
	
	cin>>n;
	memset(tree,0,sizeof(tree));
	for(int i = 1;i <= n;i++)
	{
		cin>>a[i].sf>>a[i].lz>>a[i].rz;
		tree[i][0] = a[i].lz;
		tree[i][1] = a[i].rz;
	}
	dfs(1,0);
	cout<

좋은 웹페이지 즐겨찾기