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:YA_ME_DE at 2009-05-11 22:40:15 FLOYD这的原理就是: 对S和D,枚举中点M,根据代码中if语句的判断,每次即枚举 S->M的路径中的最长值,M->D路径中的最长值,比较,取最长值,即S->D的路径的最长值。注意,这里的最长值是指单条路径最长值。 而在枚举中点的时候,S->M的最长值实际上已经在前面枚举过了,也就是有一个M',之前有S->M',然后M'->M,这样,S->M的最长值实际上之前就已经求出,在求S到D的时候再次被用到。 如果S->M的最长值跟M->D的最长值相比要大,那么最长的值就是S->M的值,反之就是M->D的。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator