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 |
其实不用拓扑排序也行的,想法也很清晰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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator