图论500题.doc

图论500题= 以下是最小生成树+并查集=【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 Eddys 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 Huangs National Road System 最小生成树+DFS4126 Genghis Khan the Conqueror 枚举+最小生成树+DFS(难)1829&poj2492 A Bugs 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_creams world II 最小树形图(要输出根有点恶心)4009 Transfer water 最小树形图(模板题)3311 Dig The Wells 斯坦纳树(状压DP)(模板题)4085Peach Blossom Spring斯坦纳树(状压DP)(有可能是森林.)2586 How far away ？LCA2874 Connections between citiesLCA3486 IntervieweRMQ2888 Check Corners二维RMQ3183A Magic LampRMQ(有点难想到,有点难联系到RMQ)【POJ】1258 Agri-Net最经典的MST1789 Truck History 最小生成树1287 Networking 简单2349 Arctic Network简单1611 The Suspects 并查集2377 kruskal2524 Ubiquitous Religions 并查集2236 Wireless Network 并查集+计算几何2560 Kruskal 并查集1861 NetWorkKruskal 3625 Building Roadsprim1679 - The Unique MST(基础) 判断MST是否唯一3522 - Slim Span(基础) 求一颗生成树，让最大边最小边差值最小2485 Highways MST中的最长边2395 最小生成树的最长边1751 Highways 求出方案POJ-1182 食物链 种类并查集POJ 1456 Supermarket贪心+区间合并POJ-1703 Find them, catch them种类并查集POJ-1988 Cube Stacking种类并查集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(难) 最小树形图poj3723Conscription 最大生成树 【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 routefloyd求最小环1839Delay Constrained.二分下限+最短路(带限制最短路)3631 Shortest Path Floyd插点法4114Disneys FastPass最短路+二维状压DP(难)3832 Earth Hour三点连通(斯坦纳树)3873 Invade the MarsDij变体(好题!,带限制最短路)4063 Aircraft几何构图+最短路4179Difficult Routesdis开二维状态的最短路(带限制最短路)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 平面图最小割(建图麻烦)3860Circuit Board平面图最小割(建图麻烦)4360 As long as Binbin loves Sangsang 拆点构图3931 cross the fire 类似于平面图最小割+拆点最短路4318 Power transmission 乘法意义下最短路【POJ】1062 昂贵的聘礼竟然可以和最短路联系起来1094 Sorting It All OutFloyd判环+拓扑排序1125 Stockbroker GrapevineFloyd1135 Domino Effect最短路,比较有意思1161 Walls最短路(图太恶心了)1502 MPI MaelstromFloyd1511 Invitation Cards来回最短路1556The Doors 计算几何+最短路1724 ROADS带限制的最短路,dis开二维来记录信息(或广搜)1734 Sightseeing tripfloyd最小环路径1797 Heavy Transportation二分枚举+最短路1847 Tram简单最短路1860Currency Exchange货币兑换1949 Chores反向建边,求最长路2139 Six Degrees of Cowvin BaconFloyd2240Arbitrage货币兑换2253Frogger二分+最短路2312 坦克大战spfa最短路本质变形-广搜2387 Til the Cows Come Home基础最短路2394Checking an Alibi最短路2449Remmarguts DateA*求第K短路2457 Part Acquisition最短路 (输出路径)2472 106 miles to Chicago乘积最短路(log一下,乘变加)2502Subway2570 Fiber Network floyd3013 圣诞树3037Skiing3072 Robot3114 Countries in War 强联通+最短路3160 Father Christmas flymouse 强联通+最长路3255 Roadblock3259 Wormholes（寻找负权回路）3268 Silver Cow Part3311 Hie with the Pie floyd+状压3328 Cliff Climbing3439 Server Relocation3463 Sightseeing 次短路条数31593521Geometric Map计算几何+最短路3549GSM phone 计算几何+最短路3594 Escort of Dr. Who How3613 Cow Relays 经过N条边的最短路 / floyd + 二分矩阵3615 Cow Hurdles3621 最优比率环3635 full tank?3660 传递闭包3662 Telephone Lines=以下是差分约束系列=Sgu 298 King Berl VI 上下界约束求最小解，三遍spfa【HDU】1384 Intervals1529 Cashier Employment1531 King1534 Schedule Problem3440 House Man3592 World Exhibition 同poj31693666 THE MATRIX PROBLEM【POJ】1201 Intervals =约束求最小，spfa求最长路1716 Integer Intervals 同上1275 Cashier Employment 二分答案验证最优解 2983 Is the Information Reliable 验证解存在3169 Layout 求满足约束的最大解，求最短路 1364 29493159 Candies 要用堆优化Dijkstra做3687 Labeling Balls 拓扑可做 =以下是二分匹配系列=普通匹配,多重匹配【HDU】1068Girls and Boys1150Machine Schedule1151Air Raid1179Ollivanders: Makers of Fine Wands since 382 BC.1281棋盘游戏149850 years, 50 colors最小点权覆盖1507Uncle Toms Inherited Land*1528Card Game Cheater1845Jimmys Assignment2063过山车2119Matrix2444The Accomodation of Students2768Cat vs. Dog3081Marriage Match II3225 Flower Placement 字典序第k小的完美匹配3360National Treasures1045也可搜索1350最小路径覆盖3118类似二分匹配3729238910542819完全匹配1668 二分+多重匹配3605多重匹配3861强连通+二分匹配 最小路径覆盖2236无题IIhdu34684185 Oil Skimming奇偶匹配【POJ】1087A Plug for UNIX1274 The Perfect Stall1469COURSES1486 Sorting Slides 二分图的必须边1548Robots1698Alices Chance1719Shooting Contest1904 Kings Quest 求二分图所有可能的匹配边2060 Taxi Cab Scheme 最小路径覆盖2112 Optimal Milking 二分+多重匹配2226 Muddy Fields 行列的覆盖2239 Selecting Courses2289 Jamies Contact Groups 二分+多重匹配2446 Chessboard2536 Gopher II2584T-Shirt Gumbo2594 Treasure Exploration 可相交最小路径覆盖2672Hotkeys2724 Purifying Machine3020 Antenna Placement3041 Asteroids 简单行列匹配，最小点权覆盖3189Steady Cow Assignment 二分+多重匹配3207 Ikkis Story IV - Pandas Trick3216 Repairing Company 最小路径覆盖3343 Against Mammoths3692 Kindergarten 二分图最大团2771 Guardian of Decency最大独立集Ural 1721 two sides of the same coin 利用矛盾条件构图最大独立集=以下是KM算法系列=【HDU】2255奔小康赚大钱1533Going Home1853Cyclic Tour3488Tour3435A new Graph Game2426Interesting Housing Problem2853Assignment3718Similarity3722Card Game3395Special Fish2282Chocolate2813One fihgt one2448Mining Station on the Sea3315My Brute3523Image copy detection【POJ】2195 Going Home 最小权值匹配2400 Supervisor, Supervisee 输出所有最小权匹配2516 Minimum Cost 最小权值匹配或最小费用流3565Ants 模型转化+简单证明3686 The Windys 最小权值匹配=以下是最大团&稳定婚姻系列=【HDU】1530Maximum Clique1435Stable Match3585maximum shortest distance 二分+最大团1522Marriage is Stable1914The Stable Marriage Problem【POJ】1129四色定理 着色问题1419最大独立集 最大团2989极大团3487 The Stable Marriage Problem 稳定婚姻=以下是强双联通系列=【HDU】强连通:1269 迷宫城堡 判断是否是一个强连通2767Proving Equivalences 至少加几条边让整个图变成强连通3836 Equivalent Sets 至少加几条边让整个图变成强连通1827 Summer Holiday 传递的最小费用3072 Intelligence System 传递的最小费用3861The Kings Problem 强连通+二分匹配3639Hawk-and-Chicken 强连通缩点 + 树形dp（累加子节点的总权值）3594 Cactus 仙人掌图双连通:2242考研路茫茫空调教室 双联通缩点+树形DP2460Network 边双连通3849By Recognizing These Guys, We Find Social Networks Useful 双连通求桥3896Greatest TC 双连通4005 The war 边双连通+DP或贪心LCA:2586How far away ？2874Connections between cities3078Network LCA+排序3830Checkers 二分+LCA【POJ】强连通:1236Network of Schools2553 The Bottom of a Graph 好题！ 找出度为0的集合2186 Popular Cows 好题！ 找出度为0的，其他分量都指向它的集合2375Cow 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 强连通+最短路3592Instantaneous Transference 强连通分量+最长路1904Kings Quest 强连通双连通：3694 Network 边双连通 (同hdu2460)3177 Redundant Paths 构造边双连通3352 Road Construction 构造边双连通2942 Knights of the Round Table (点双连通经典题)1515 Street Directions (无向图改有向图)1438 One-way Traffic (混合图改有向图)LCA:1330Nearest Common Ancestors1470Closest Common Ancestors1986Distance Queries3417Network3728The merchant LCA+并查集,更新询问2763Housewife Wind LCA+树状数组=以下是2-SAT系列=【HDU】3062 Party1824 Lets go home3622 Bomb Game3715 Go Deeper 二分+2-sat验证1815 Building roads2723 Get Luffy Out1816 Get Luffy Out *1814 Peaceful Commission4115 Eliminate the Conflict【POJ】2296 Map Labeler2723 Get Luffy Out 判断性2749 Building roads3207 Ikkis Story IV - Pandas Trick 判断性3648 Wedding spj方案3678 Katu Puzzle 异或操作3683 Priest Johns Busiest Day 输出方案3905 Perfect Election=以下是欧拉回路系列=【HDU】1878欧拉回路 判断3018Ant Trip 一笔画问题11162894兹鼓欧拉回路1956 3472混合欧拉【POJ】1041 Johns trip 欧拉回路1386 Play on Words 单词接龙2230Watchcow 欧拉回路2513 Colored Sticks 无向图欧拉路2337 Catenyms 欧拉路径1392 Ouroboros Snake 兹鼓欧拉回路1780 code1237 The Postal Worker Rings Once 无向图CPP（简单）2404 Jogging Trails 无向图CPP（状压）1637 SightSeeing Tour混合欧拉，网络流流量守恒【zoj】1992=以下是拓扑排序系列=【HDU】1285确定比赛名次2094产生冠军2647Reward3342Legal or Not有向图判环1811 Rank of Tetris 拓扑+并查集3231 Box Relations 三维拓扑【POJ】1094 Sorting It All Out Floyd+拓扑2367 Genealogical tree3660 Cow Contest 拓扑序一定的元素3687 Labeling Balls 字典序最小的拓扑，补图1128 Frame Stacking DFS版拓扑1270Following Orders 拓扑+回溯1420Spreadsheet 模拟拓扑2762Going from u to v or from v to u? 强连通+拓扑3553Task schedule=以下是竞赛图系列=竞赛图下的哈密顿问题Strange Country IIZOJ-3332Task SequencesPOJ-1776The book SGU-122 DiracTour RoutePOJ-3780 SPJ出问题了，与下题相同Tour RouteHDOJ-3414=以下是网络流系列=【HDU】1532Drainage Ditches(基础)最大流3549Flow Problem(基础)最大流3572Task Schedule最大流任务分配,判断满流2732Leapin Lizards最大流3338Kakuro Extension最大流数和最大流行进列出2883kebab最大流判断满流3605Escape最大流多重匹配 归类构图3081Marriage Match II二分最大流+并查集3277Marriage Match III二分最大流同上,多了拆点3416Marriage Match IV最大流最短路+最大流2485Destroying the bus stations最短路+最大流不正确!，应该是费用流找增广路3599 War 最短路+最大流3468Treasure Hunting最大流(二分匹配)+最短路3551Hard Problem最大流x 一般图匹配3998Sequence(难)DP+最大流最长上升子序列 不相交路径数目3917Road constructions最大权闭包3879Base Station最大权闭包3061Battle最大权闭包3996Gold Mine最大权闭包3472HS BDC混合欧拉4183 来回走不重复点的网络流.4309 Seikimatsu Occult Tonneru 枚举构图-1533Going Home(基础)费用流3488Tour费用流圈3435A new Graph Game费用流圈1853Cyclic Tour费用流圈2686Matrix费用流3376Matrix Again费用流3667Transportation费用流拆边3315My Brute费用流(可用KM)3395Special Fish费用流(可用KM匹配)2448Mining Station on the Sea费用流(可用最短路+KM匹配)4067Random Maze(难)费用流3947River Problem(难)费用流神奇费用流,流量不等式建图4322 Candy 费用流神奇构图3046Pleasant sheep and big big wolf 最小割3987 Harry Potter and the Forbidden Forest 边数最少最小割1565方格取数(1)最小割1569方格取数(2)最小割3820Golden Eggs最小割方格加强3491Thieves最小割平面图S-T最小割3657Game最小割最大点权独立集3313Key Vertex最小割3251Being a Hero最小割4313 Matrix 最小割化简矩阵构图3157Crazy Circuits上下流3002King of Destruction全局最小割3691Nubulsa Expo全局最小割【POJ】1087A Plug for UNIX 最大流(可用二分匹配)1274The Perfect Stall 最大流(可用二分匹配)1325Machine Schedule最大流(可用二分匹配)1698Alices Chance最大流(可用二分匹配)2239Selecting Courses最大流(可用二分匹配) MLE 2446Chessboard最大流(可用二分匹配) 好题啊2536Gopher II最大流(可用二分匹配)2771Guardian of Decency最大流二分匹配最大独立集3041 Asteroids 最大流(简单二分匹配)2584 T-Shirt Gumbo 最大流(多重匹配)3189 Steady Cow Assignment(中等)二分最大流(多重匹配)1149 PIGS 最大流 绝对经典的构图题1273 Drainage Ditches 最大流(基础)1459 Power Network(基础)最大流2711 Leapin Lizards 最大流3281 Dining 最大流2112 Optimal Milking(基础) 二分最大流2289 Jamies Contact Groups 二分最大流2391 Ombrophobic Bovines(中等) 二分最大流2455 Secret Milking Machine(基础) 二分最大流3228 Gold Transportation 二分最大流(并查集)2699 The Maximum Number of Strong Kings(较难) 枚举人数 + 最大流3498March of the Penguins(中等) 最大流枚举汇点,满足点容量限制的网络流2987 Firing(较难) 最大权闭包1637 Sightseeing tour(Crazy) 混合欧拉2135 Farm Tour 费用流 (来回最短路)2175Evacuation Plan(中等) 费用流 消圈2195Going Home费用流2516 Minimum Cost 费用流3422 Kakas Matrix Travels(中等) 费用流拆点3680 Intervals(较难) 费用流经典,费用流+离散化3686The Windys费用流(KM匹配)3762The Bonus Salary!费用流1815 Friendship(中等) 最小割最小点割集1966 Cable TV Network(中等) 最小割最小点割集2125 Destroying The Graph(难) 最小割最小点