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

Re:想了一下好像想通了

Posted by YA_ME_DE at 2009-05-11 22:55:33 on Problem 2253
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:
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