Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:AC了,说一下思路。In Reply To:AC了,说一下思路。 Posted by:taolei0628 at 2009-11-21 03:32:52 > 数学基础不好,不太会用数学符号,全用文字表达。 > 侦探是点,助手是有向边。根是L. > 原理:如果存在两条从根到多有点的生成树,那么除根以外的所有点,一定存在两条以上的边到达它。 > (1)先生成一个从根到达所有点的树 T1。 > (2)在剩余边中生成从根到达包含所有可到达点的树 T2 > (3) 如果T2包含所有点,YES. > (4) 可证明T2包含的所有点至少有两条边可到达其余点,而他们一定在T1中,否则NONE.选择其中一个尽量不包含根的边:a->b,a在T2中,b在其他点中.(尽量不要包含根,否则有可能失败,这个没想清楚原因) > (5) 可证明在T2以外的边中一定存在另外一条不通过a->b也能从根到达b的路径(因为b有两个以上入边,而T2不存在到达b的路径),否则NONE。重新生成T1,使T1不通过T2的边和a->b,可证明T1同样可以包含所有点。 > (6) 把a->b加入T2中,继续生成T2. > (7) 重复(3)-(6)的步骤,每次循环T1包含所有点,而T2不断增长。如果存在两条从根到多有点的生成树,T1、T2必然最终可到达所有点。 似乎不行呢。。。。 反例: 5 12 3 5 3 3 2 4 2 1 4 3 2 5 4 3 1 2 3 T1取边:3 6 8 11 T2取边:1 3 然后取a=3, b=4(即边6) 问题在于:“可证明在T2以外的边中一定存在另外一条不通过a->b也能从根到达b的路径” Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator