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 fish_ball at 2008-03-17 12:49:43 on Problem 1094
In Reply To:这里放些数据出来,有疑问的基本上都能解决~我郁闷了好久才发现 Posted by:fish_ball at 2008-03-17 12:40:43
做一个邻接矩阵,开始全部标记-1
标记通为 1,断为 0
新增一条有向边 E<V1,V2>

label_1:

如果已经标记为 0,则标记一个矛盾

如果已经标记为-1,则是一个已知的关系,跳过

然后如果未标记,标记 E<V1,V2> = 1,E<V2,V1> = 0;
并且,考察所有 V1 的入度以及 V2 的出度
如果存在 E<V3,V1>,则回到 label_1 考察 E<V3,V2>
如果存在 E<V2,V3>,则回到 label_1 考察 E<V1,V3>

这个过程是可以用递归解决的,并且,每标记一个新的边,计数count++
那么,确定所有关系的条件就是 count = N * ( N - 1 ) / 2

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