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 |
Re:向量根本没有命中要害,我以为,不如说是用并查集维护一个传递可推导关系……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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator