最短路 http://acm.hdu.edu.cn/showproblem.php?pid=2544
赤裸裸的最短路
A Walk Through the Forest http://acm.hdu.edu.cn/showproblem.php?pid=1142
"He considers taking a path from A to B to be progress if there exists a route from B to his home that is shorter than any possible route from A." 重在理解這句話(huà)。先求出所有頂點(diǎn)到頂點(diǎn)2的最短路(以頂點(diǎn)2為源點(diǎn)做一次Dijkstra)，然后從頂點(diǎn)1開(kāi)始記憶化搜索。
If (d[u] > d[v])
Sum += bfs(v);
Minimum Transport Cost http://acm.hdu.edu.cn/showproblem.php?pid=1385
Floyd路徑輸出，題目要按路徑的字典序輸出；
if (p[i][k] + p[k][j] == map[i][j] && path[i][k] < path[i][j])
path[i][j] = path[i][k];
即可
Arbitrage http://acm.hdu.edu.cn/showproblem.php?pid=1217
問(wèn)題是是否可以盈利，如果我們把匯率看成邊，當(dāng)一個(gè)點(diǎn)通過(guò)某些路徑返回到自己后的值大于1，則盈利；
A strange lift http://acm.hdu.edu.cn/showproblem.php?pid=1548
因?yàn)檫叺臋?quán)值都為1，BFS，Dijkstra都可以
一個(gè)人的旅行http://acm.hdu.edu.cn/showproblem.php?pid=2066
需要構(gòu)圖，另外建立2個(gè)點(diǎn)，分別各乘車(chē)城市，草兒想去的地方相連，權(quán)值為0；則問(wèn)題轉(zhuǎn)化為單源最短路問(wèn)題；
The shortest path http://acm.hdu.edu.cn/showproblem.php?pid=2224
Bitonic path (詳見(jiàn)《算法導(dǎo)論》 P217)
一個(gè)人從p1嚴(yán)格地增的走到pn，然后再?lài)?yán)格遞減的回到p1;求總路徑的最小值；
網(wǎng)上看到很多解題報(bào)告
看的我直冒汗
對(duì)于1 <= i <= j <= n, 我們定義P(i, j)是一條包含了P1, P2, P3 …… Pj的途徑; 這條路徑可以分成2部分：遞減序列與遞增序列，起點(diǎn)是Pi(1 <= i <= j)，拐點(diǎn)是P1，終點(diǎn)是Pj, P[i, j]為其最小值；那么狀態(tài)轉(zhuǎn)移方程為：
b[1,2] = |P1P2|,
i < j-1時(shí)， b[i,j] = b[i,j-1] + |Pj-1Pj| 點(diǎn)Pj-1在遞增序列中，
i = j-1時(shí)， b[i,j] = min{ b[k,j-1] + |PkPj|, 1<= k < j-1 } 點(diǎn)Pj-1在遞減序列中
b[n,n] = b[n-1,n] + |Pn-1Pn|
The Shortest Path http://acm.hdu.edu.cn/showproblem.php?pid=2807
Floyd與多次Dijkstra都可以；
A*B=C, A,C連同；
我們不妨可以對(duì)于每?jī)蓚€(gè)城市相乘，把得到的矩陣跟非A，B比較，而不要對(duì)于A,C去尋找是否存在這樣一個(gè)B，結(jié)果很容易超時(shí)
另外，這里有個(gè)優(yōu)化是矩陣的比較 （2維轉(zhuǎn)化成1維）
posted on 2009-12-04 17:12
西風(fēng)蕭瑟 閱讀(2633)
評(píng)論(1) 編輯 收藏 引用 所屬分類(lèi):
圖論