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 |
关于此题1、最大流可以有相同的点,而此题除起点和终点外,要求路径中的点都不同,所以此题不会是最大流? 2、联想到点双连通,最小割点集合的大小为1(1个割点),也就是2-连通,任意两点之间至少有2条路径可达(应该是经过不同的边),此题要求3-连通,我类推一下就觉得应该是删除了某个割点集合中的点后此图仍然是点双连通的。 枚举删除每个点,用tarjan判断是否存在割点即可。 3、我的写法没有考虑两点之间的重边,应该是数据里没有吧,如果有重边的话,在点双连通里重边是无效的(等于没有)吧。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator