알고리즘 훈련 노드 선택
n 개의 노드 가 있 는 나무 가 있 고 나무의 모든 노드 에 정수 값 이 있 습 니 다.만약 한 점 이 선택 된다 면, 나무 위 에서 그것 과 인접 한 점 은 모두 선택 할 수 없다.선택 한 점 의 가중치 와 최대 가 얼마 입 니까?
입력 형식
첫 줄 에는 정수 n 이 포함 되 어 있 습 니 다.
다음 줄 은 n 개의 정수, i 의 정수 가 점 i 의 가중치 를 대표 합 니 다.
다음은 모두 n - 1 줄 입 니 다. 줄 마다 나무의 한 변 을 설명 합 니 다.
출력 형식
선택 한 점 의 가중치 와 최대 치 를 나타 내 는 정 수 를 출력 합 니 다.
샘플 입력
5 1 2 3 4 5 1 2 1 3 2 4 2 5
샘플 출력
12
예시 설명
3, 4, 5 번 점, 가중치 와 3 + 4 + 5 = 12 를 선택 하 십시오.
데이터 규모 와 약정
20% 의 데이터 에 대해 n < = 20.
50% 의 데이터 에 대해 n < = 1000.
100% 의 데이터 에 대해 n < = 100000.
가중치 가 모두 1000 을 넘 지 않 는 정수 다.
생각:
트 리 동적 계획 문제 의 가장 중요 한 두 단 계 는 먼저 나 무 를 만 든 다음 에 동적 계획 을 하 는 것 이다.
(1) 이것 은 뿌리 가 없 는 다 진 트 리 로 인접 표 법 으로 저장 할 수 있 습 니 다. 포인터 의 사용 번 거 로 움 을 피하 기 위해 배열 로 대체 합 니 다. head [maxn] 저장 헤드 노드 번호 로 list [2 * manx]. vex 로 인접 점 도 메 인 을 저장 하고 list [2 * maxn]. next 로 체인 도 메 인 을 저장 합 니 다.
(2) 뿌리 가 없 기 때문에 어느 노드 든 뿌리 로 삼 을 수 있 습 니 다. y [i] 로 i 번 째 뿌리 를 선택 하 는 가중치 와 n [i] 로 i 번 째 뿌리 를 선택 하지 않 는 가중치 와 i 번 째 뿌리 를 선택 했다 고 가정 하면 아 이 를 선택 할 수 없습니다. 만약 에 i 번 째 뿌리 를 선택 하지 않 으 면 아 이 를 선택 할 수 있 습 니 다 (아 이 를 선택 할 수도 있 고 손 자 를 선택 할 수도 있 습 니 다).
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 5;
int m, cnt = 0;
int y[maxn] = {0}, n[maxn] = {0}, w[maxn], head[maxn] = {0}, vis[maxn] = {0};
struct ArcNode
{
int vex, next;
}list[2 * maxn];
// ，
void Insert(int u, int v)
{
list[++cnt].vex = v;
list[cnt].next = head[u];
head[u] = cnt;
list[++cnt].vex = u;
list[cnt].next = head[v];
head[v] = cnt;
}
void Dp(int root)
{
vis[root] = 1;
for(int i = head[root]; i != 0; i = list[i].next)
{
if(vis[list[i].vex] == 0)
{
Dp(list[i].vex);
y[root] += n[list[i].vex];
n[root] += max(y[list[i].vex], n[list[i].vex]);
}
}
y[root] += w[root];
}
int main()
{
int i, j, u, v, ans;
scanf("%d", &m);
for(i = 1; i <= m; i++)
scanf("%d", &w[i]);
for(j = 1; j <= m - 1; j++)
{
scanf("%d%d", &u, &v);
Insert(u, v);
}
Dp(1);
ans = max(y[1], n[1]);
printf("%d
", ans);
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
