[BZOJ 2060] [Usaco 2010 Nov] Visiting Cows 젖소 방문
http://www.lydsy.com/JudgeOnline/problem.php?id=2060
제목 의 대의
한 그루 의 나 무 를 지정 합 니 다. 각 변 은 하나의 점 만 방문 할 수 있 습 니 다. 최대 방문 을 물 어보 십시오.
해제
기본 트 리 DP
var
dp:array[0..50005,0..1]of longint;
x:array[0..50005]of longint;
w:array[0..150005,1..2]of longint;
i,j,k:longint;
n,len,a,b,tt:longint;
procedure init(a,b:longint);
begin
w[len,1]:=b;
if w[a,2]=0
then w[a,2]:=len else w[w[a,1],2]:=len;
w[a,1]:=len; inc(len);
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure dfs(a:longint);
var tt:longint;
begin
x[a]:=1; tt:=w[a,2]; dp[a,1]:=1; dp[a,0]:=0;
while tt<>0 do
begin
if x[w[tt,1]]=0 then begin
dfs(w[tt,1]);
dp[a,1]:=dp[a,1]+dp[w[tt,1],0];
dp[a,0]:=dp[a,0]+max(dp[w[tt,1],1],dp[w[tt,1],0]);
end;
tt:=w[tt,2];
end;
end;
begin
readln(n); len:=n+1;
for i:=1 to n-1 do
begin
readln(a,b);
init(a,b); init(b,a);
end;
dfs(1);
writeln(max(dp[1,1],dp[1,0]));
end.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
