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

树形DP……水过。

Posted by 597100700 at 2011-10-07 22:18:11 on Problem 1985
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