Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:树形DP……水过。

Posted by snowing0427 at 2011-12-15 22:51:40 on Problem 1985
In Reply To:树形DP……水过。 Posted by:597100700 at 2011-10-07 22:18:11
> var a,b,c,d,e,m,n,sum,max:longint;
>     f1,f2:array[0..100000]of longint;
>     list,next,cost,toit:array[0..1000000]of longint;
>     ch:char;
> procedure make(i,j,k:longint);
> begin
> inc(sum);
> toit[sum]:=j;
> next[sum]:=list[i];
> cost[sum]:=k;
> list[i]:=sum;
> end;
> procedure dfs(i,j:longint);
> var ii,jj,kk:longint;
> begin
> f1[i]:=0;f2[i]:=0;
> ii:=list[i];
> while ii<>0 do
>  begin
>  if toit[ii]<>j then
>  begin
>  dfs(toit[ii],i);
>  if f1[toit[ii]]+cost[ii]>f1[i] then
>   begin
>   f2[i]:=f1[i];
>   f1[i]:=f1[toit[ii]]+cost[ii];
>   end
>   else if f1[toit[ii]]+cost[ii]>f2[i] then f2[i]:=f1[toit[ii]]+cost[ii];
>  end;
>  ii:=next[ii];
>  end;
> end;
> begin
> readln(n,m);
> for a:=1 to m do
>  begin
>  readln(b,c,d);
>  make(b,c,d);
>  make(c,b,d);
>  end;
> dfs(1,0);
> for a:=1 to n do
>  if f1[a]+f2[a]>max then
>   max:=f1[a]+f2[a];
> writeln(max);
> end.

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator