Detail of message

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

关于本题

Posted by bigyellow at 2008-12-18 11:08:40 on Problem 1062
In Reply To:首先：这道题只用考虑交易中的最高等级和最低等级之差不超过m即可 Posted by:bigyellow at 2008-12-18 10:58:38

首先，本题等级只用考虑交易的人中最高和最低等级之差不超过M即可；
其次，这道题类似于单源点最短路径，可以用bellman_ford或者dijstra，需要注意的是必须按照酋长等级进行枚举；没有枚举的dijstra运气好可以过的，但是我开始用的bellman_ford，所以wa了无数编，比如考虑如下数据
1 5
10000 2 2
2 800
3 700
1000 2 1
4 500
1000 3 1
4 400
1000 2 1
5 100
50 1 0
正解是1450;

另外，由于数据范围并不是太大，所以用DFS反而很简便，可以很方便解决等级问题，效率也不差
我用的DFS :504K	0MS可以过，只是剪枝的时候尽量多考虑，最好能求出下界，不然会MLE

希望对没有过的同学有帮助