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

这题qsort+二分可否?请各位进来看看这个方法是不是有错误?

Posted by edward2 at 2009-06-28 16:16:40 on Problem 2513
我老WA- -。。。开始怀疑是否算法问题了。。。
我的做法是先qsort颜色,然后删掉重复的颜色。
然后枚举边,用二分找到相应的点,用邻接表表示边。
然后找一个出度比入度大1的点(如果没有找到,则取任意一个点)出发看能否到达全图。
如果不能表示不连通,输出Impossible
如果能连通,则看是否
1.没有出度和入度不相等的点
或
2.有且仅有一个出度比入度大1的点和一个入度比出度大1的点。
有则输出Possible
否则输出Impossible

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