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

Re:向量根本没有命中要害,我以为,不如说是用并查集维护一个传递可推导关系……

Posted by forgetEver at 2012-09-30 13:10:09 on Problem 1182
In Reply To:向量根本没有命中要害,我以为,不如说是用并查集维护一个传递可推导关系…… Posted by:Sayakiss at 2012-05-06 16:58:14
> 给定一个对称的二元关系(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