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 Sayakiss at 2012-05-06 16:58:14 on Problem 1182 and last updated at 2012-05-06 17:03:00
In Reply To:总结此题可以精简到一个并查集!并且用向量的思考模式想整个过程相当简单! Posted by:majiaN at 2008-10-19 10:58:32
给定一个对称的二元关系(symmetric)R,关系中的每个元素有一个权值函数V.
若对于任意的
(a,b) in R
(b,c) in R
如果存在一个函数F,使得V(a,c)=F[V(a,b),V(b,c)]
则称该关系传递可推导。

该题显然满足以上条件。
对于A吃B 则V((A,B))=1 V((B,A))=-1
对于A和B同类 则V((A,B))=0 V((B,A))=0
F[V1,V2]=(V1+V2)%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