昂貴的聘禮 http://acm.pku.edu.cn/JudgeOnline/problem?id=1062
Dijkstra算法就可以了，權(quán)非負(fù)；
有的物品對應(yīng)有替代品 + 優(yōu)惠價(jià)格，反過來考慮，即替代物品 + 優(yōu)惠價(jià)格就達(dá)到原來的物品，建圖；
增加一個(gè)頂點(diǎn)，連接每個(gè)頂點(diǎn)，權(quán)值等于該頂點(diǎn)的價(jià)值，相當(dāng)于你直接支付；
難點(diǎn)在于等級限制M； 枚舉 + 刪頂點(diǎn)；
因?yàn)槟阕詈笫冀K要到達(dá)頂點(diǎn)1，滿足等級限制條件還要訪問頂點(diǎn) 1？
一次枚舉 (lv[1] - M) ~ lv[1]，……，lv[1] ~ (lv[1] + M) ，把不符合條件的頂點(diǎn)給予visit[i]=1;
Stockbroker Grapevine http://acm.pku.edu.cn/JudgeOnline/problem?id=1125
考察flyod算法，先求出每個(gè)點(diǎn)到其他頂點(diǎn)的距離，然后選出其中的最大值，即為這個(gè)點(diǎn)到達(dá)所有頂點(diǎn)的最大距離；如果最大值為初始化的INF，則該點(diǎn)不能到達(dá)所有點(diǎn)；
然后再從能到達(dá)所有點(diǎn)中的集合點(diǎn)選出最小值；
Invitation Cards http://acm.pku.edu.cn/JudgeOnline/problem?id=1511
對SPFA鄰接表實(shí)現(xiàn)的考察，bellman_ford,dijkstra都會(huì)超時(shí)；
求每個(gè)志愿者來回的最短路，ccs -> x -> ccs,前一部分由正向圖對頂點(diǎn)1做一次單源最短路即可，建立逆向圖再次求解就是第二部分；
Currency Exchange http://acm.pku.edu.cn/JudgeOnline/problem?id=1860
Bellman_ford算法；從銀行實(shí)現(xiàn)2種貨幣的兌換可以認(rèn)為每種貨幣相當(dāng)于一個(gè)頂點(diǎn)，每家銀行相當(dāng)于連接兩個(gè)頂點(diǎn)的一條邊；求是否存在一條路徑u -> a -> b -> …… u，權(quán)值之和大于原來的值；
MPI Maelstrom http://acm.pku.edu.cn/JudgeOnline/problem?id=1502
Heavy Transportation http://acm.pku.edu.cn/JudgeOnline/problem?id=1797
Arbitrage http://acm.hdu.edu.cn/showproblem.php?pid=1217
同HDU 1217
Frogger http://acm.pku.edu.cn/JudgeOnline/problem?id=2253
Til the Cows Come Home http://acm.pku.edu.cn/JudgeOnline/problem?id=2387
Wormholes http://acm.pku.edu.cn/JudgeOnline/problem?id=3259
Silver Cow Party http://acm.pku.edu.cn/JudgeOnline/problem?id=3268
Big Christmas Tree http://acm.pku.edu.cn/JudgeOnline/problem?id=3013
Skiing http://acm.pku.edu.cn/JudgeOnline/problem?id=3037
Candies http://acm.pku.edu.cn/JudgeOnline/problem?id=3159
Cow Hurdles http://acm.pku.edu.cn/JudgeOnline/problem?id=3615
Cow Contest http://acm.pku.edu.cn/JudgeOnline/problem?id=3660
posted on 2009-12-05 17:10
西風(fēng)蕭瑟 閱讀(1988)
評論(0) 編輯 收藏 引用 所屬分類:
圖論