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

等一分钟,或许下一分钟,谣言传遍全stockbrokers

Posted by imzhangliang at 2009-03-18 16:18:04 on Problem 1125
发这个帖子表示惊讶,没想到这样直观天真的方式也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:
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