在做PKU2762時,需要建鄰接表。于是按部就班寫了下面一個插入邊到鄰接表中的函數(shù):
完成完整的程序提交上去,得到結(jié)果Memory:25796K Time:375MSLanguage:C++ Result:Accepted再對比別人的程序Memory:296K Time:109MS無論是時間還是空間都相差很大。于是就考慮怎么優(yōu)化自己的程序。第一個問題:規(guī)模只有1000,為什么會用那么多內(nèi)存呢?仔細一想數(shù)據(jù)是多case的,每次插入新節(jié)點時都要動態(tài)創(chuàng)建一個節(jié)點。一來動態(tài)創(chuàng)建耗時間,二來每個case結(jié)束的鄰接表中的節(jié)點沒有釋放,故耗費大量內(nèi)存。然后就想到了下面的算法,首先初始化一塊內(nèi)存Graph use[100*VMAX];這樣每次需要新節(jié)點時,就從use中獲取。如果use使用完畢就再動態(tài)創(chuàng)建。依此算法優(yōu)化后,得到的結(jié)果比較滿意Memory:1000K Time:218MSLanguage:C++ Result:Accepted