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

关于此题

Posted by yuanchuanshun at 2012-08-09 09:39:44 on Problem 3713
1、最大流可以有相同的点,而此题除起点和终点外,要求路径中的点都不同,所以此题不会是最大流?

2、联想到点双连通,最小割点集合的大小为1(1个割点),也就是2-连通,任意两点之间至少有2条路径可达(应该是经过不同的边),此题要求3-连通,我类推一下就觉得应该是删除了某个割点集合中的点后此图仍然是点双连通的。

枚举删除每个点,用tarjan判断是否存在割点即可。

3、我的写法没有考虑两点之间的重边,应该是数据里没有吧,如果有重边的话,在点双连通里重边是无效的(等于没有)吧。

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