=============================以下是最小生成树+并查集======================================

【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