[kuangbin带你飞]专题四 最短路练习
[kuangbin帶你飛]專題四 最短路練習
專題鏈接
推薦關于圖論的刷題
A - Til the Cows Come Home poj-2387
題意：
有n個點，t條路，給出每條路的長度，問怎么走能使得從起點走到終點路路程最短。
難度：
2顆星，單源最短路徑，dijkstra模板
題解：
兩種解法見此
B - Frogger poj-2253
題意：
給n個點的坐標，問如何走使得最長邊最短。
也就是給了點圖，找最小生成樹的最大邊。
C - Heavy Transportation poj-1797
題意：
有n個點m條邊，要構建一個經過一個能從節點1到節點n的最大路（樹），使的最小邊最大，建最大生成樹。
題解：
（一）用krustral 的做最大生成樹
D - Silver Cow Party
題意：
n頭牛，分別在n塊田野上，他們都要到X這塊田野上，給出的邊是有向邊，每條邊會花費牛t的時間，問花費時間最長的牛最少要花費多少。
題解：
(一)
用1次dijkstra，以x為起點，找出x到各個點的最短時間，得到每頭牛回去的時間。
再用n-1次dijkstra，分別各個點為起點，找出各個點到x的最短時間，得到每頭牛去的最短時間。
這樣就可以得到每頭牛的來回時間。
（二）
正向建圖，得到以x為起點，到達各個點的最短時間，即回去的時間。
方向建圖，得到以各個點為起點，到達x的最短時間，即前去的時間。
E.Currency Exchange poj-1860
題意：
有n種貨幣，m種交易方式，每次交換都有一定的比率，還要付手續費，問最終經過交換能否賺錢。
題解：
bellon判斷存在正權環否
經過交換回到起點，起點值變大，那就是走一個問存在一個正環否。用Bellon 算法。
F.Wormholes poj- 3259
題解：
判斷是否純正負權環
感覺測評機很有問題，不想做可以跳
E.MPI Maelstrom poj-1502
題解：
dijkstra裸題，只是題難讀而已。
??: H - Cow Contest
?
難度：
3顆星
簡單卻是一道好題，將最短路的應用延伸為傳遞閉包 傳遞閉包簡單理解
題意：
n頭牛兩兩對決m場，問從這些場次中確定排行的牛有幾頭。
題解：
排名確定，也就是說這頭牛與其他所有牛的關系確定了，與其他牛的關系要么是被擊敗了，要么是擊敗其他牛了。
轉化成路的思想，也就 a與其他牛i，a能到i或者i能到a。如果有1頭牛與a的關系不明確，也就不能知道這頭牛的排名了。
I - Arbitrage
題意：
貨幣交易轉換。
問是否存在一種情況，當前有一種1單元的1種貨幣，經過轉換之后，又重新回到了得到了這種貨幣，而金額上升。
題解：
poj 2240 floyd題解
J - Invitation Cards
題意：
n-1個人從1號點出發，到剩余n-1個宣傳點，然后再回到1號點匯報結果，求所有人往返路徑和的最小值
題解：
正向+反向dijkstra
K - Candies
題意：
有n個人，m組數a,b,c，表示b不可以比a多 c個，問最終分配，使得序號1的與序號n的差距數最大為多少。
題解：
最短路
雖然想要讓1和n的差距最大，也就是路程最遠，可是給定的路徑全部要滿足，那也就是要滿足小的，也就是每次都挑最小的走，那也就是按最短路走到達n。
L -Subway poj-2502
題意：
走路10km/h，坐公交車40km/h
給出家和學校的位置，又給出幾條公交車會停靠的站點。問最少用幾分鐘能到學校。
題解：
建圖麻煩的dijkstra。
輸出的是時候要這樣處理。
int ans=(int)(best[2]+0.5);M -昂貴的聘禮 poj-1062
題意：
交換物品，使得最終用最少的錢換到目標物，且交換的對象之間的階級不能超過m。
題解：
1號能被2號到，又能被3號換到，2號又能被其他換到，那就是一個源點出發，求最短路徑。
代碼見此
wa點：
與之交易的人 范圍不能超過m，但是酋長不被要求在哪個范圍里。
Tram poj-1847
題意：
拿樣例說
3 2 1 2 2 3 2 3 1 2 1 2有3個路口，司機當前在2號路口，想要去1號路口。
第2行表示，如果司機在1號路口，有2個選擇，0次操作去2號路口，1次操作去3號路口。剩下2行也是此意思。
問司機的最少操作數是多少。
題解：
典型的最短路。
Extended Traffic LightOJ - 1074
題解：
spfa
有負權邊，求最短路。
if(change[a]==n||best[a]<3||best[a]==inf)printf("?\n");3種情況打印？-----
1.change[a]==n 有負環，這時不存在最短路。
2.best[a]?? gives total earning less than 3
3.best[a]=inf 不可到達
總結
以上是生活随笔為你收集整理的[kuangbin带你飞]专题四 最短路练习的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 合并多个DataTable统计数据
- 下一篇： 节日才需要快乐吗？