SDNU__1015. 가장 먼 경로
1200 단어 SDNUOJ
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<