kthtree問(wèn)題
給定一棵有向樹(shù)T，樹(shù)T 中每個(gè)頂點(diǎn)u都有一個(gè)權(quán)w(u)；樹(shù)的每條邊(u,v)也都有一個(gè)
非負(fù)邊長(zhǎng)d(u,v)。有向樹(shù)T的每個(gè)頂點(diǎn)u 可以看作客戶，其服務(wù)需求量為w(u)。每條邊(u,v)的邊長(zhǎng)d(u,v) 可以看作運(yùn)輸費(fèi)用。如果在頂點(diǎn)u 處未設(shè)置服務(wù)機(jī)構(gòu)，則將頂點(diǎn)u 處的服務(wù)需求沿有向樹(shù)的邊(u,v)轉(zhuǎn)移到頂點(diǎn)v 處服務(wù)機(jī)構(gòu)需付出的服務(wù)轉(zhuǎn)移費(fèi)用為w(u)*d(u,v)。
樹(shù)根處已設(shè)置了服務(wù)機(jī)構(gòu)，現(xiàn)在要在樹(shù)T中增設(shè)k處服務(wù)機(jī)構(gòu)，使得整棵樹(shù)T 的服務(wù)轉(zhuǎn)移費(fèi)用最小
標(biāo)簽：
kthtree
樹(shù)
上傳時(shí)間：
2013-12-21
上傳用戶：lyy1234
