poj1848

【题意】

给定一颗n（n<=100）个点的树，求让每个在且只在一个环上最少需要添加的边数（一个环上起码要有三个点）

【输入】

第一行一个数n

接下来n行每行描述一条边

【输出】

如题意的答案

树形动态规划

每个点记录三个状态

0表示包括该点的子树全部在环上的最小代价

1表示该点在一条起码有两个点链上且除这条链上的点都在环上的最小代价

2表示该点在为链的起点且子数上的点全部在环上的最小代价

转移部分十分麻烦

program poj1848;
const
  inf=maxlongint div 100;
var
  tot,n,i,j,k,u,v:longint;
  root:array [0..101] of longint;
  next,point:array [0..201] of longint;
  f:array [0..2,0..101] of longint;

function min (a,b:longint):longint;
begin
  if a<b then exit(a)
         else exit(b);
end;

procedure connect (u,v:longint);
begin
  inc(tot);
  point[tot]:=v;
  next[tot]:=root[u];
  root[u]:=tot;
end;

procedure dfs (now,father:longint);
var
  i,sum,first,second,q,p:longint;
begin
  i:=root[now];
  first:=0;
  second:=0;
  sum:=0;
  q:=0;
  p:=0;
  while i<>0 do
    begin
      if point[i]<>father then
        begin
          dfs(point[i],now);
          sum:=sum+f[0,point[i]];
          if -f[0,point[i]]+f[1,point[i]]<-f[0,first]+f[1,first] then
            begin
              second:=first;
              first:=point[i];
            end
                                                                 else
          if -f[0,point[i]]+f[1,point[i]]<-f[0,second]+f[1,second] then
            second:=point[i];
          if -f[0,point[i]]+min(f[1,point[i]],f[2,point[i]])<
          -f[0,q]+min(f[1,q],f[2,q]) then
            begin
              p:=q;
              q:=point[i];
            end
                                     else
          if -f[0,point[i]]+min(f[1,point[i]],f[2,point[i]])<
          -f[0,p]+min(f[1,p],f[2,p]) then
            p:=point[i];
        end;
      i:=next[i];
    end;
  f[2,now]:=sum;
  if first=0 then
    begin
      f[0,now]:=inf;
      f[1,now]:=inf;
      exit;
    end;
  if second=0 then
    begin
      f[0,now]:=f[1,first]+1;
      f[1,now]:=min(f[1,first],f[2,first]);
      exit;
    end;
  f[0,now]:=min(sum-f[0,first]+f[1,first]+1,
  sum-f[0,q]+min(f[1,q],f[2,q])-f[0,p]+min(f[1,p],f[2,p])+1);
  f[1,now]:=sum-f[0,q]+min(f[1,q],f[2,q]);
end;

begin
  read(n);
  tot:=0;
  for i:=1 to n - 1 do
    begin
      read(u,v);
      connect(u,v);
      connect(v,u);
    end;
  f[1,0]:=maxlongint div 10;
  f[2,0]:=maxlongint div 10;
  dfs(1,0);
  if f[0,1]>=inf then writeln(-1)
                 else writeln(f[0,1]);
end.