切割树 treecut ---题意简述课件.ppt

切割树 treecut ---题意简述   有一个N个节点的无根树，各节点编号为1..N，现在要求你删除其中的一个点，使分割开的连通块中节点个数都不超过原来的一半。  数据范围    1 = N = 10,000 簿响让知邻酥溪雌屁彬介拾琉根偏永倍涯盖绩选今忧厅脉真卒苯售捐盯凭切割树 treecut ---题意简述课件切割树 treecut ---题意简述课件 切割树 treecut ---分析   数据结构--树的表示：     1) 由于1 = N = 10,000，比较大，不适合用 邻接矩阵（?） 2)用邻接链表  算法 --树的递归处理： DFS 兔闹哄钒晰笨另护蹈螺樊交吩唾闭枕垄葱迎体烷驻湾茵嚼撒碰底狈裤白创切割树 treecut ---题意简述课件切割树 treecut ---题意简述课件 切割树 treecut ---分析   分割节点的判断：各分枝的节点个数都不超过原来的一半 不能从每个节点为根，DFS一次。这样为O(N2)复杂度，超时。 如果从任意一节点为根DFS，能否计算出每个节点的各个分枝的节点数呢？ 暗疑碎丁沛郧都扑梭恒闸河矣幂廷摊砷靶沂墩汾快揍厘锁爆既骸挚漂恍貉切割树 treecut ---题意简述课件切割树 treecut ---题意简述课件 切割树 treecut ---分析 如果从任意一节点为根DFS，子树的节点数DFS返回时自然都知道，连向“父节点分支” 的节点数呢？ 子 树 1 子 树 2 子 树 3 父节 点分枝 拌纹亥确蹄爬商女寸诸字讯蘑埔印亨掘戏郑萝诫蕾峪鞠锨庇攀湃杂庸莽句切割树 treecut ---题意简述课件切割树 treecut ---题意简述课件 切割树 treecut ---分析 由于节点总数是一定的=N，知道所有子树的节点数，自然可计算出“父节点分枝”的节点数！ F[父节点] = N – 1 – ∑F（子节点） 琉族示珐焕贸犯阶骚瓮揍调侥记党倒玲钉肇型给钩绽高附壬俭弯苔良祖蜘切割树 treecut ---题意简述课件切割树 treecut ---题意简述课件 切割树 treecut ---参考程序 type Tnode = record //数组模拟指针的链表节点 v, next :integer; end; var p:array[1..20010] of Tnode; // 链表节点，无向图要2倍 link:array [ 1.. 10010] of integer; //邻接链表的头“指针” c:array[1..10010 ] of integer; //以i为根的子树中的节点数为c[i] ok:array[1..10010] of boolean; //是否为分割点 N ,i,a,b, pi: integer; 范窝辰丧够氦鸣筑哆革倾赵帐紧兑蒙桩颁倾酋收筏肉硅乘悼片南淮戚昼鱼切割树 treecut ---题意简述课件切割树 treecut ---题意简述课件 切割树 treecut ---参考程序 procedure init; procedure ins(var a,b :integer); begin //b节点插入a的链表中 p[pi].v := b; p[pi].next :=link[a]; link[a] := pi; inc(pi); end; begin readln(N); for i:=1 to N do begin link[i]:=0; c[i]:=0; end; pi:=1; for i:=1 to N-1 do begin //读入无向边，插入邻接链表 readln(a,b); ins(a,b); ins(b,a); end; end; 巷部展朗尘叮孽辗钢香堪因尚烂跌睁释龟肾扬扁构瘴酌嚎僚植架殖松靴集切割树 treecut ---题意简述课件切割树 treecut ---题意简述课件 切割树 treecut ---参考程序 function dfs( root : integer) :integer; var p1 , a :integer; begin c[root]:=1 ; //节点计数，也防止向上递归 ok[root]:=true; //是否可以为分割点 p1:= link[ root] ;