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

没看题目,单看解释就觉得很帅 Orz

Posted by ziliang at 2007-01-04 22:56:10 on Problem 3163
In Reply To:见内 Posted by:flymouse at 2007-01-01 20:59:46
>     因为数据规模的问题(N<=10,M<=10000),给人的第一感觉会是集合DP.但是集合DP是O(M*N*2^N)的时间复杂度,是超时的.然后我们会想到KM匹配,但是边数为10000*10,显然还是很大……细细地看一下题目,N的规模非常小,M的规模非常大.那么,我们很容易想到缩小M的规模.因为对于sempr的每一个人物来说,他只可能匹配到styc的M个人物中的对他胜率最大的N个人物中的一个,所以styc的每个人物只需要向外连接N条边就可以了,这样,如果顶点不重复,那么最多就是N*N个点,那么就是N个点和N*N个点做KM匹配,因为N很小,所以很容易解决.对于解决乘法,可以把所有的边log一下,最后再exp即可。当然了,一种更快的做法就是:首先排序,sempr的每个人物选择10个对他胜率最大的,然后变成了一个10×100的图,然后做一下集合DP。

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