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 |
等一分钟,或许下一分钟,谣言传遍全stockbrokers发这个帖子表示惊讶,没想到这样直观天真的方式也0ms过,而且没算disjoint。可能数据真的很弱。我以为这样的方法就算正确也会超时之类的。 用的方法是从每个人开始穷举比较。 算每个人开始总共需要的时间用的是过一分钟(计数加1,可以计算计数最大应该是990),刷新一次stockbrokers之间传递的状态(状态用2唯数组表示,a[i][j]表示i到j点还需要走的时间)。可以把stockbrokers的状态看成是电流的传递(当然电流不可能这么慢)。用一个list表示真正传递的人,当有一个新知道谣言的人,知道谣言的人数+=1,这个人加进散布的list(插入的时候放在list头,因为这一分钟还没过,新人还没有资格传递谣言),当一个传完所有他身边的人被list删除, 如果所有人都知道谣言了或者list上没有真正散布谣言的人,计时结束。 如果所有人都知道谣言,计时有效。比较最小值。 如果所有即时都没效,就是disjoint btw: 虽然想法好像容易直观的想出来,但是数据结构的写还是很烦啊,调试了n次,自己的基本功太弱了。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator