【题意】
给定一颗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.