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

Re:AC了,说一下思路。

Posted by jiangh33 at 2011-10-14 19:34:55 on Problem 3745
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:
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