轉自——http://blog.csdn.net/qwe20060514/article/details/8112550

?

=============================以下是最小生成樹+并查集======================================
【HDU】
1213 ??How Many Tables???基礎并查集★
1272 ??小希的迷宮???基礎并查集★
1325&&poj1308 ?Is It A Tree????基礎并查集★
1856 ??More is better???基礎并查集★
1102 ??Constructing Roads??基礎最小生成樹★
1232 ??暢通工程???基礎并查集★
1233 ??還是暢通工程???基礎最小生成樹★
1863 ??暢通工程???基礎最小生成樹★
1875 ??暢通工程再續???基礎最小生成樹★
1879 ??繼續暢通工程???基礎最小生成樹★
3371??? ?Connect the Cities? ??簡單最小生成樹★
1301 ??Jungle Roads???基礎最小生成樹★
1162 ??Eddy's picture???基礎最小生成樹★
1198 ??Farm Irrigation???基礎最小生成樹★
1598 ??find the most comfortable road?枚舉+最小生成樹★★
1811 ??Rank of Tetris???并查集+拓撲排序★★
3926 ??Hand in Hand???同構圖★
3938 ??Portal? ???離線+并查集★★
2489??? ?Minimal Ratio Tree ??dfs枚舉組合情況+最小生成樹★
4081??? ?Qin Shi Huang's National Road System 最小生成樹+DFS★★???
4126??? ?Genghis Khan the Conqueror ?枚舉+最小生成樹+DFS(難)★★★★???

1829&&poj2492 ?A Bug's Life???基礎種類并查集★*
1558 ??Segment set???計算幾何+并查集★
3461 ??Code Lock???并查集(有點難想到)★★
3367 ??Pseudoforest???最大生成樹★
2473 ??Junk-Mail Filter??并查集+設立虛父節點(馬甲)★★
3172 ??Virtual Friends???帶權并查集★
3635 ??Dragon Balls???帶權并查集★
3047 ??Zjnu Stadium???帶權并查集★
3038 ??How Many Answers Are Wrong?種類并查集★★
2818 ??Building Block???帶權并查集★
3234 ??Exclusive-OR???異或并查集(難)★★★
2121??? ?Ice_cream’s world II? ??最小樹形圖(要輸出根有點惡心)★★
4009??? ?Transfer water ???最小樹形圖(模板題)★
3311? ??Dig The Wells??? ?斯坦納樹(狀壓DP)(模板題)★★
4085??Peach Blossom Spring??斯坦納樹(狀壓DP)(有可能是森林...)★★★

2586 ??How far away ？???LCA★
2874 ??Connections between cities?LCA★
3486 ??Interviewe???RMQ★
2888 ??Check Corners???二維RMQ★
3183??A Magic Lamp???RMQ(有點難想到,有點難聯系到RMQ)★★

【POJ】
1258 ??????最經典的MST★
1789 ??Truck History ???最小生成樹★
1287 ??Networking ???簡單★
2349 ??Arctic Network???簡單★
1611 ??The Suspects ???并查集★
2377 ??????kruskal★
2524 ??Ubiquitous Religions ??并查集★
2236 ??Wireless Network ??并查集+計算幾何★
2560 ??????Kruskal 并查集★
1861 ??????Kruskal ★
3625 ??????prim★
1679 - ??The Unique MST(基礎)? ??判斷MST是否唯一★
3522 - ??Slim Span(基礎)? ??求一顆生成樹，讓最大邊最小邊差值最小★
2485 ??Highways ???MST中的最長邊★
2395 ??????最小生成樹的最長邊★
1751 ??Highways ???求出方案★
POJ-1182 ?食物鏈 ????種類并查集★★
POJ 1456 ?Supermarket???貪心+區間合并★
POJ-1703 ?????種類并查集★
POJ-1988 ?????種類并查集★
POJ-1733 ?Parity game ???種類并查集，先要離散化一下，不影響結果★
POJ-1417 ?True Liars(難) ???并查集+DP 種類并查集★★
POJ-2912 ?Rochambeau(難) ???baidu的題,很不錯...是食物鏈的加強版.判斷裁判比較難想.★★★
POJ 2728 ?Desert King(中等)? ??最優比率生成樹★★
POJ 1639 ?Picnic Planning(較難) ??頂點度數有限制的最小生成樹★★
POJ 3164 ?Command Network(難) ??最小樹形圖★★

poj3723??????好題!!! ★★
poj3228??????好好題!!! ★★

【ZOJ】
ZOJ-3261 逆向并查集 ★★

?

===============================以下是最短路系列====================================
【HDU】
1548??? ?A strange lift???基礎最短路(或bfs)★
2544??? ?最短路? ???基礎最短路★
3790?? ??最短路徑問題???基礎最短路★
2066?? ?? 一個人的旅行???基礎最短路(多源多匯,可以建立超級源點和終點)★
2112??? ?HDU Today???基礎最短路★
1874??? ?暢通工程續???基礎最短路★
1217??? ?Arbitrage?? ???貨幣交換 Floyd (或者 Bellman-Ford 判環)★
1245??? ?Saving James Bond??計算幾何+最短路★
1317??? ?XYZZY? ????Bellman-Ford判環,有負權★
1535??? ?Invitation Cards?? ??有向圖的來回最短路,(反向建圖)★
1546??? ?Idiomatic Phrases Game? ?最短路★
2680??? ?Choose the best route?? ?最短路★
2923??? ?Einbahnstrasse???最短路★
3339??? ?In Action? ???最短路+背包★
2224??? ?The shortest path??雙調旅行商問題★★
2807??? ?The Shortest Path??矩陣運算+最短路(floyd)★★
1595??? ?find the longest of the shortest枚舉+最短路(刪掉任意一條邊的最長最短路)★★
3986??? ?Harry Potter and the Final Battle 枚舉+最短路(刪掉任意一條邊的最長最短路)★★
1599??? ?find the mincost route??floyd求最小環★
1839??Delay Constrained...??二分下限+最短路(帶限制最短路)★★?
3631 ??Shortest Path?????????????????? Floyd插點法★★
4114??Disney's FastPass??最短路+二維狀壓DP(難)★★★
3832??? ?Earth Hour???三點連通(斯坦納樹)★
3873??? ?Invade the Mars???Dij變體(好題!,帶限制最短路)★★★
4063 ??Aircraft???幾何構圖+最短路★★★★

hdu4179??Difficult Routes??dis[][]開二維狀態的最短路(帶限制最短路)★★

1869 ??六度分離 ???Floyd最短路★
1385??? ?Minimum Transport Cost??? ?最短路+輸出路徑(輸出字典序最小路徑,有點惡心)★★?
1224??? ?free DIY Tour ???最短路+輸出路徑★
1142??? ?A Walk Through the Forest? ?最短路+記憶搜索★★
1596??? ?find the safest road?? ??乘積最小的最短路★
1598??? ?find the most comfortable road?二分速度差+最短路(帶限制最短路)★★
2722??? ?Here We Go(relians) Again?最短路★
2962??? ?Trucking? ???二分+最短路(帶限制最短路)★★
1690??? ?Bus System ???最短路★
2433??? ?Travel????刪邊+最短路之和(預處理橋邊)★★★???
2363??? ?Cycling????二分+最短路(帶限制最短路)★★
2377??? ?Bus Pass???最短路(尋找一個點的最長最短路最小)★★
2833??? ?WuKong????最短路+記憶化搜索(求兩條最短路的最多公共點)★★
1688??? ?Sightseeing???最短次短路條數★★
3191??? ?How Many Paths Are There?次短路條數★★
2482??? ?Transit search???最短路★★★
3768 ??Shopping???最短路+dfs(或最短路+狀壓DP)★★
3035??? ?War????平面圖最小割(建圖麻煩)★★
3870??? ?Catch the Theves ??平面圖最小割(建圖麻煩)★★
3860??Circuit Board???平面圖最小割(建圖麻煩)★★

【POJ】
1062 ??昂貴的聘禮???竟然可以和最短路聯系起來★★
1094 ??Sorting It All Out??Floyd判環+拓撲排序★
1125??Stockbroker Grapevine??Floyd★
1135 ??Domino Effect???最短路,比較有意思★★
1161 ??Walls????最短路(圖太惡心了)★★
1502 ??MPI Maelstrom???Floyd★
1511??? ?Invitation Cards??來回最短路★
1556??The Doors? ???計算幾何+最短路★★
1724 ??ROADS????帶限制的最短路,dis[][]開二維來記錄信息(或廣搜)★★
1734 ??Sightseeing trip??floyd最小環路徑★
1797 ??Heavy Transportation??二分枚舉+最短路★
1847 ??Tram????簡單最短路★
1860??Currency Exchange??貨幣兌換★
1949 ??Chores????反向建邊,求最長路★★
2139 ??Six Degrees of Cowvin Bacon?Floyd★
2240??Arbitrage???貨幣兌換★
2253??Frogger????二分+最短路★
2312 ??坦克大戰???spfa最短路本質變形-->廣搜★
2387 ??Til the Cows Come Home??基礎最短路★
2394??Checking an Alibi??最短路★
2449??Remmarguts' Date??A*求第K短路★★
2457 ??Part Acquisition??最短路 (輸出路徑)★★
2472 ??106 miles to Chicago??乘積最短路(log一下,乘變加)★★

2502??Subway
2570 ??Fiber Network floyd
3013 ??圣誕樹
3037??Skiing
3072 ??Robot
3114 ??Countries in War ??強聯通+最短路
3160 ??Father Christmas flymouse ?強聯通+最長路
3255 ??Roadblock
3259 ??Wormholes???（尋找負權回路）
3268 ??Silver Cow Part
3311 ??Hie with the Pie ??floyd+狀壓
3328 ??Cliff Climbing
3439 ??Server Relocation
3463 ??Sightseeing ???次短路條數
3159?
3521??Geometric Map???計算幾何+最短路
3549??GSM phone ???計算幾何+最短路
3594 ??Escort of Dr. Who How
3613 ??Cow Relays? ???經過N條邊的最短路 // floyd + 二分矩陣
3615 ??Cow Hurdles
3621 ??最優比率環
3635 ??full tank?
3660 ??傳遞閉包
3662 ??Telephone Lines
============================以下是差分約束系列============================
【HDU】
1384 ??Intervals
1529 ??Cashier Employment
1531 ??King
1534 ??Schedule Problem
3440 ??House Man
3592 ??World Exhibition
3666 ??THE MATRIX PROBLEM

【POJ】
1201
1275
1364
1716
2949
2983
3159
3169
3687

============================以下是二分匹配系列============================
普通匹配,多重匹配

【HDU】

1068??Girls and Boys
1150??Machine Schedule
1151??Air Raid
1179??Ollivanders: Makers of Fine Wands since 382 BC.
1281??棋盤游戲
1498??50 years, 50 colors
1507??Uncle Tom's Inherited Land*
1528??Card Game Cheater
1845??Jimmy’s Assignment
2063??過山車
2119??Matrix
2444??The Accomodation of Students
2768??Cat vs. Dog
3081??Marriage Match II
3360??National Treasures
1045??也可搜索
1350??最小路徑覆蓋
3118??類似二分匹配
3729
2389
1054
2819??完全匹配
1668 ??二分+多重匹配
3605??多重匹配
3861??強連通+二分匹配
2236??無題II

hdu3468
hdu4185?奇偶匹配

?

【POJ】
1087??A Plug for UNIX
1274 ??The Perfect Stall
1469??COURSES
1486 ??Sorting Slides ???二分圖的必須邊
1548??Robots
1698??Alice's Chance
1719??Shooting Contest
1904 ??King's Quest ???求二分圖所有可能的匹配邊
2060 ??Taxi Cab Scheme ??最小路徑覆蓋
2112 ??Optimal Milking ??二分+多重匹配
2226 ??Muddy Fields ???行列的覆蓋
2239 ??Selecting Courses
2289 ??Jamie's Contact Groups?? 二分+多重匹配
2446 ??Chessboard
2536 ??Gopher II
2584??T-Shirt Gumbo
2594 ??Treasure Exploration ??可相交最小路徑覆蓋
2672??Hotkeys
2724 ??Purifying Machine
3020 ??Antenna Placement
3041 ??Asteroids ???簡單行列匹配?
3189??Steady Cow Assignment ??二分+多重匹配
3207 ??Ikki's Story IV - Panda's Trick
3216 ??Repairing Company
3343 ??Against Mammoths
3692 ??Kindergarten
2771??????最大獨立集
============================以下是KM算法系列============================
【HDU】
2255??奔小康賺大錢
1533??Going Home
1853??Cyclic Tour
3488??Tour
3435??A new Graph Game
2426??Interesting Housing Problem
2853??Assignment
3718??Similarity
3722??Card Game
3395??Special Fish
2282??Chocolate
2813??One fihgt one
2448??Mining Station on the Sea
3315??My Brute
3523??Image copy detection

【POJ】
2195 ??Going Home ???最小權值匹配
2400 ??Supervisor, Supervisee ??輸出所有最小權匹配
2516 ??Minimum Cost ???最小權值匹配或最小費用流
3565??Ants
3686 ??The Windy's ???最小權值匹配
?
============================以下是最大團&穩定婚姻系列============================
【HDU】

1530??Maximum Clique
1435??Stable Match
3585??maximum shortest distance ?二分+最大團
1522??Marriage is Stable
1914??The Stable Marriage Problem

【POJ】

1129??四色定理 著色問題
1419??最大獨立集
2989??極大團
3487 ??The Stable Marriage Problem 穩定婚姻
============================以下是強雙聯通系列============================
【HDU】
強連通:
1269? ??迷宮城堡? ???判斷是否是一個強連通
2767??Proving Equivalences? ??至少加幾條邊讓整個圖變成強連通
3836 ??Equivalent Sets? ??至少加幾條邊讓整個圖變成強連通
1827?? ??Summer Holiday? ??傳遞的最小費用
3072??? ?Intelligence System? ??傳遞的最小費用
3861??The King’s Problem ??強連通+二分匹配
3639??Hawk-and-Chicken? ??強連通縮點 + 樹形dp（累加子節點的總權值）
3594 ??Cactus ????仙人掌圖

雙連通:
2242??考研路茫茫——空調教室? ?雙聯通縮點+樹形DP
2460??Network???? 邊雙連通
3849??By Recognizing These Guys, We Find Social Networks Useful? 雙連通求橋
3896??Greatest TC? ???雙連通
4005 ??The war? ???邊雙連通

LCA:
2586??How far away ？
2874??Connections between cities
3078??Network? ???LCA+排序
3830??Checkers? ???二分+LCA

【POJ】
強連通:
1236??Network of Schools
2553 ??The Bottom of a Graph? ??好題！ 找出度為0的集合
2186??? ?Popular Cows? ???好題！ 找出度為0的，其他分量都指向它的集合
2375??Cow Ski Area ???強連通
2762??? ?Going from u to v or from v to u?? 縮點+拓撲排序
3160?? ??Father Christmas flymouse? ?強連通+最短路
3180 ??The Cow Prom? ???判斷有幾個環， 分量中元素大于1的個數
3114??Countries in War? ??強連通+最短路
3592??Instantaneous Transference? ?強連通分量+最長路
1904??King's Quest? ???強連通+并查集?
???
雙連通：
3694 ??Network? ???邊雙連通 (同hdu2460)
3177 ??Redundant Paths?? ??構造邊雙連通
3352 ??Road Construction?? ??構造邊雙連通
2942 ??Knights of the Round Table? (點雙連通經典題)
1515 ??Street Directions ??(無向圖改有向圖)
1438 ??One-way Traffic? ??(混合圖改有向圖)

LCA:
1330??Nearest Common Ancestors
1470??Closest Common Ancestors
1986??Distance Queries
3417??Network
3728??The merchant? ???LCA+并查集,更新詢問
2763??Housewife Wind ???LCA+樹狀數組
============================以下是2-SAT系列============================
【HDU】
3062 ??Party
1824 ??Let's go home
3622 ??Bomb Game
3715 ??Go Deeper
1815 ??Building roads
2723 ??Get Luffy Out
1816 ??Get Luffy Out *
1814 ??Peaceful Commission
4115 ??Eliminate the Conflict

?

【POJ】
2296 ??Map Labeler
2723 ??Get Luffy Out
2749? ??Building roads
3207? ??Ikki's Story IV - Panda's Trick
3648 ??Wedding
3678 ??Katu Puzzle
3683? ??Priest John's Busiest Day
3905 ??Perfect Election
============================以下是歐拉回路系列============================
【HDU】
1878??歐拉回路? 判斷
3018??Ant Trip 一筆畫問題
1116
2894??茲鼓歐拉回路
1956
3472??混合歐拉

【POJ】
2513? ??????歐拉路
1041? ??John's trip? ???歐拉回路
1386 ??Play on Words? ???單詞接龍
2230??Watchcow? ???歐拉回路
2513 ??Colored Sticks? ??無向圖歐拉路
2337 ??Catenyms? ???歐拉路徑
1392 ??Ouroboros Snake? ??茲鼓歐拉回路
1780? ??code
1637? ??????混合歐拉

【zoj】
1992
============================以下是拓撲排序系列============================
【HDU】?
1285??確定比賽名次
2094??產生冠軍
2647??Reward
3342??Legal or Not
1811??Rank of Tetris? ??拓撲+并查集
3231 ??????三維拓撲

【POJ】
1094 ??Sorting It All Out? ??Floyd+拓撲
2367 ??Genealogical tree
3660 ??Cow Contest
3687 ??Labeling Balls ???神奇的拓撲
1128??Frame Stacking? ??DFS版拓撲
1270??Following Orders? ??拓撲+回溯
1420??Spreadsheet? ???模擬拓撲
2762??Going from u to v or from v to u?? 強連通+拓撲
3553??Task schedule
============================以下是競賽圖系列============================
競賽圖下的哈密頓問題

Strange Country II?ZOJ-3332
Task Sequences?POJ-1776
The book?SGU-122
Tour Route?POJ-3780
Tour Route?HDOJ-3414
============================以下是網絡流系列============================
【HDU】

?

1532??Drainage Ditches(基礎)??[最大流]
3549??Flow Problem(基礎)??[最大流]
3572??Task Schedule???[最大流]任務分配,判斷滿流?
2732??Leapin' Lizards(難)??[最大流]
3338??Kakuro Extension??[最大流][數和]神奇最大流行進列出
2883??kebab????[最大流]判斷滿流
3605??Escape????[最大流](多重匹配
3081??Marriage Match II??[二分最大流]+并查集
3277??Marriage Match III??[二分最大流]同上,多了拆點
3416??Marriage Match IV??[最大流]最短路+最大流
2485??Destroying the bus stations?[最大流]最短路+最大流
3468??Treasure Hunting??[最大流](二分匹配)+最短路
3551??Hard Problem???[最大流]
3998??Sequence(難)???[DP+最大流]最長上升子序列
3917??Road constructions??[最大權閉包]
3879??Base Station???[最大權閉包]
3061??Battle????[最大權閉包]
3996??Gold Mine???[最大權閉包]
3472??HS BDC????[混合歐拉]
hdu4183?來回走不重復點的網絡流.
-------------------------
1533??Going Home(基礎)??[費用流]
3488??Tour????[費用流]圈
3435??A new Graph Game??[費用流]圈
1853??Cyclic Tour???[費用流]圈
2686??Matrix????[費用流]
3376??Matrix Again???[費用流]
3667??Transportation???[費用流]拆邊
3315??My Brute???[費用流](可用KM)
3395??Special Fish???[費用流](可用KM匹配)
2448??Mining Station on the Sea?[費用流](可用最短路+KM匹配)
4067??Random Maze(難)???[費用流]
3947??River Problem(難)??[費用流]神奇費用流,流量不等式建圖
3046??Pleasant sheep and big big wolf [最小割]
1565??方格取數(1)???[最小割]
1569??方格取數(2)???[最小割]
3820??Golden Eggs???[最小割]方格加強
3491??Thieves????[最小割]最小點割集
3657??Game????[最小割]最大點權獨立集
3313??Key Vertex???[最小割]
3251??Being a Hero???[最小割]?
3157??Crazy Circuits???[上下流]
3002??King of Destruction??[全局最小割]
3691??Nubulsa Expo???[全局最小割]
【POJ】
1087??A Plug for UNIX? ??[最大流](可用二分匹配)
1274??The Perfect Stall ??[最大流](可用二分匹配)
1325??Machine Schedule??[最大流](可用二分匹配)
1698??Alice's Chance???[最大流](可用二分匹配)
2239??Selecting Courses??[最大流](可用二分匹配)
2446??Chessboard???[最大流](可用二分匹配) 好題啊
2536??Gopher II???[最大流](可用二分匹配)
2771??Guardian of Decency??[最大流]二分匹配最大獨立集
3041 ??Asteroids ???[最大流](簡單二分匹配)
2584 ??T-Shirt Gumbo ???[最大流](多重匹配)
3189 ??Steady Cow Assignment(中等)?[二分最大流](多重匹配)
1149 ??PIGS? ????[最大流] 絕對經典的構圖題
1273 ??Drainage Ditches? ??[最大流](基礎)
1459 ??Power Network(基礎)??[最大流]
3281 ??Dining ????[最大流]
2112 ??Optimal Milking(基礎)? ??[二分最大流]
2289 ??Jamie's Contact Groups ??[二分最大流]
2391 ??Ombrophobic Bovines(中等) ?[二分最大流]
2455 ??Secret Milking Machine(基礎) ?[二分最大流]
3228 ??Gold Transportation ??[二分最大流](并查集)
2699 ??The Maximum Number of Strong Kings(較難)? [枚舉人數 + 最大流]
3498??March of the Penguins(中等)? ?[最大流]枚舉匯點,滿足點容量限制的網絡流
2987 ??Firing(較難)? ???[最大權閉包]
1637 ??Sightseeing tour(Crazy)? ?[混合歐拉]
2135 ??Farm Tour? ???[費用流] (來回最短路)
2175??Evacuation Plan(中等) ??[費用流] 消圈
2195??Going Home???[費用流]
2516 ??Minimum Cost ???[費用流]
3422 ??Kaka's Matrix Travels(中等)? ?[費用流]拆點
3680 ??Intervals(較難)? ??[費用流]經典,費用流+離散化
3686??The Windy's???[費用流](KM匹配)
3762??The Bonus Salary!??[費用流]
1815 ??Friendship(中等)? ??[最小割]最小點割集
1966? ??Cable TV Network(中等)? ?[最小割]最小點割集
2125 ??Destroying The Graph(難)? ?[最小割]最小點權覆蓋
3084 ??Panic Room(中等，好題)? ?[最小割]邊連通度
3204 ??Ikki's Story I - Road Reconstruction(基礎) [最小割]求關鍵邊
3308 ??Paratroopers(較難) ??[最小割]乘積取對數,最小點權覆蓋
3436??ACM Computer Factory??[最小割]收集流,殘留搜集找邊
3469 ??Dual Core CPU(中等)? ??[最小割]收集流
3921??Destroying the bus stations?[最小割]點連通
2396 ??Budget(中等)? ???[有源匯的上下界可行流]
3155 ??Hard Life(很挑戰一題)? ??[最大密度子圖]
2914??Minimum Cut???[無向圖最小割]
============================以下是dancing links系列============================
1001??Easy Finding???POJ-3740
1002??Power Stations???HDOJ-3663
1003??Treasure Map???ZOJ-3209
1004??Lamp????HDOJ-2828
1005??whosyourdaddy???HDOJ-3498
1006??Bomberman - Just Search!?HDOJ-3529
1007??Square Destroyer??POJ-1084
1008??Matrix????HDOJ-2119
1009??Divisibility???HDOJ-3335
1010??Radar????HDOJ-2295
1011??Fire station???HDOJ-3656
1012??Repair Depots???HDOJ-3156
1013??Dominoes???HDOJ-2518
1014??Street Fighter???HDOJ-3957
1015??Sudoku Killer???HDOJ-1426
1016??Sudoku????POJ-2676
1017??Sudoku????POJ-3074
1018??Sudoku????POJ-3076
1019??Su-Su-Sudoku???HDOJ-2780
1020??Sudoku????HDOJ-3111
1021??Sudoku????HDOJ-3909
1022??Squiggly Sudoku???HDOJ-4069
1023??Triangle War II???ZOJ-3038
1024??A Puzzling Problem??HDOJ-1603
1025??Maximum Clique???HDOJ-1530
hust1017 ?????精確覆蓋。
fzu1686,nuaa1507 ????重復覆蓋。
hit2199,2882,2959 ????精確覆蓋(數獨)。
SPOJ1771?????精確覆蓋(N皇后問題)。
poj3435

轉載于:https://www.cnblogs.com/mypride/p/4600938.html

總結

以上是生活随笔為你收集整理的【转载】图论 500题——主要为hdu/poj/zoj的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。