Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"349652743","updateTime":1542626025000,"title":"【转】各大oj经典图论题目","dislikeCnt":0,"content":"从今天开始要做一名图论选手啦\n转自大佬博客的总结,一定会认认真真刷题的,嗯!\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d以下是最小生成树+并查集\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n【HDU】\n*1213 How Many Tables 基础并查集★\n*1272 小希的迷宫 基础并查集★\n*1325\u0026\u0026poj1308 Is It A Tree? 基础并查集★\n*1856 More is better 基础并查集★\n*1102 Constructing Roads 基础最小生成树★\n*1232 畅通工程 基础并查集★\n*1233 还是畅通工程 基础最小生成树★\n*1863 畅通工程 基础最小生成树★\n*1875 畅通工程再续 基础最小生成树★\n*1879 继续畅通工程 基础最小生成树★\n*3371 Connect the Cities 简单最小生成树★\n*1301 Jungle Roads 基础最小生成树★\n*1162 Eddy’s picture 基础最小生成树★\n*1198 Farm Irrigation 基础最小生成树★\n*1598 find the most comfortable road 枚举+最小生成树★★\n*1811 Rank of Tetris 并查集+拓扑排序★★\n3926 Hand in Hand 同构图★\n3938 Portal 离线+并查集★★\n2489 Minimal Ratio Tree dfs枚举组合情况+最小生成树★\n4081 Qin Shi Huang’s National Road System 最小生成树+DFS★★\n4126 Genghis Khan the Conqueror 枚举+最小生成树+DFS(难)★★★★\n\n\n*1829\u0026\u0026poj2492 A Bug’s Life 基础种类并查集★\n1558 Segment set 计算几何+并查集★\n3461 Code Lock 并查集(有点难想到)★★\n3367 Pseudoforest 最大生成树★\n2473 Junk-Mail Filter 并查集+设立虚父节点(马甲)★★\n3172 Virtual Friends 带权并查集★\n3635 Dragon Balls 带权并查集★\n3047 Zjnu Stadium 带权并查集★\n3038 How Many Answers Are Wrong 种类并查集★★\n2818 Building Block 带权并查集★\n3234 Exclusive-OR 异或并查集(难)★★★\n2121 Ice_cream’s world II 最小树形图(要输出根有点恶心)★★\n4009 Transfer water 最小树形图(模板题)★\n3311 Dig The Wells 斯坦纳树(状压DP)(模板题)★★\n4085 Peach Blossom Spring 斯坦纳树(状压DP)(有可能是森林…)★★★\n\n\n*2586 How far away ? LCA★\n*2874 Connections between cities LCA★\n3486 Interviewe RMQ★\n2888 Check Corners 二维RMQ★\n3183 A Magic Lamp RMQ(有点难想到,有点难联系到RMQ)★★\n\n\n【POJ】\n1258 最经典的MST★\n1789 Truck History 最小生成树★\n1287 Networking 简单★\n2349 Arctic Network 简单★\n1611 The Suspects 并查集★\n2377 kruskal★\n2524 Ubiquitous Religions 并查集★\n2236 Wireless Network 并查集+计算几何★\n2560 Kruskal 并查集★\n1861 Kruskal ★\n3625 prim★\n1679 - The Unique MST(基础) 判断MST是否唯一★\n3522 - Slim Span(基础) 求一颗生成树,让最大边最小边差值最小★\n2485 Highways MST中的最长边★\n2395 最小生成树的最长边★\n1751 Highways 求出方案★\nPOJ-1182 食物链 种类并查集★★\nPOJ 1456 Supermarket 贪心+区间合并★\nPOJ-1703 种类并查集★\nPOJ-1988 种类并查集★\nPOJ-1733 Parity game 种类并查集,先要离散化一下,不影响结果★\nPOJ-1417 True Liars(难) 并查集+DP 种类并查集★★\nPOJ-2912 Rochambeau(难) baidu的题,很不错…是食物链的加强版.判断裁判比较难想.★★★\nPOJ 2728 Desert King(中等) 最优比率生成树★★\nPOJ 1639 Picnic Planning(较难) 顶点度数有限制的最小生成树★★\nPOJ 3164 Command Network(难) 最小树形图★★\n\n\npoj3723 好题!!! ★★\npoj3228 好好题!!! ★★\n\n\n【ZOJ】\nZOJ-3261 逆向并查集 ★★\n\n\n\n\n\n\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d以下是最短路系列\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n【HDU】\n1548 A strange lift 基础最短路(或bfs)★\n2544 最短路 基础最短路★\n3790 最短路径问题 基础最短路★\n2066 一个人的旅行 基础最短路(多源多汇,可以建立超级源点和终点)★\n2112 HDU Today 基础最短路★\n1874 畅通工程续 基础最短路★\n1217 Arbitrage 货币交换 Floyd (或者 Bellman-Ford 判环)★\n1245 Saving James Bond 计算几何+最短路★\n1317 XYZZY Bellman-Ford判环,有负权★\n1535 Invitation Cards 有向图的来回最短路,(反向建图)★\n1546 Idiomatic Phrases Game 最短路★\n2680 Choose the best route 最短路★\n2923 Einbahnstrasse 最短路★\n3339 In Action 最短路+背包★\n2224 The shortest path 双调旅行商问题★★\n2807 The Shortest Path 矩阵运算+最短路(floyd)★★\n1595 find the longest of the shortest枚举+最短路(删掉任意一条边的最长最短路)★★\n3986 Harry Potter and the Final Battle 枚举+最短路(删掉任意一条边的最长最短路)★★\n1599 find the mincost route floyd求最小环★\n1839 Delay Constrained… 二分下限+最短路(带限制最短路)★★\n3631 Shortest Path Floyd插点法★★\n4114 Disney’s FastPass 最短路+二维状压DP(难)★★★\n3832 Earth Hour 三点连通(斯坦纳树)★\n3873 Invade the Mars Dij变体(好题!,带限制最短路)★★★\n4063 Aircraft 几何构图+最短路★★★★\n\n\nhdu4179 Difficult Routes dis[][]开二维状态的最短路(带限制最短路)★★\n\n\n1869 六度分离 Floyd最短路★\n1385 Minimum Transport Cost 最短路+输出路径(输出字典序最小路径,有点恶心)★★\n1224 free DIY Tour 最短路+输出路径★\n1142 A Walk Through the Forest 最短路+记忆搜索★★\n1596 find the safest road 乘积最小的最短路★\n1598 find the most comfortable road 二分速度差+最短路(带限制最短路)★★\n2722 Here We Go(relians) Again 最短路★\n2962 Trucking 二分+最短路(带限制最短路)★★\n1690 Bus System 最短路★\n2433 Travel 删边+最短路之和(预处理桥边)★★★\n2363 Cycling 二分+最短路(带限制最短路)★★\n2377 Bus Pass 最短路(寻找一个点的最长最短路最小)★★\n2833 WuKong 最短路+记忆化搜索(求两条最短路的最多公共点)★★\n1688 Sightseeing 最短次短路条数★★\n3191 How Many Paths Are There 次短路条数★★\n2482 Transit search 最短路★★★\n3768 Shopping 最短路+dfs(或最短路+状压DP)★★\n3035 War 平面图最小割(建图麻烦)★★\n3870 Catch the Theves 平面图最小割(建图麻烦)★★\n3860 Circuit Board 平面图最小割(建图麻烦)★★\n\n\n【POJ】\n1062 昂贵的聘礼 竟然可以和最短路联系起来★★\n1094 Sorting It All Out Floyd判环+拓扑排序★\n1125 Stockbroker Grapevine Floyd★\n1135 Domino Effect 最短路,比较有意思★★\n1161 Walls 最短路(图太恶心了)★★\n1502 MPI Maelstrom Floyd★\n1511 Invitation Cards 来回最短路★\n1556 The Doors 计算几何+最短路★★\n1724 ROADS 带限制的最短路,dis[][]开二维来记录信息(或广搜)★★\n1734 Sightseeing trip floyd最小环路径★\n1797 Heavy Transportation 二分枚举+最短路★\n1847 Tram 简单最短路★\n1860 Currency Exchange 货币兑换★\n1949 Chores 反向建边,求最长路★★\n2139 Six Degrees of Cowvin Bacon Floyd★\n2240 Arbitrage 货币兑换★\n2253 Frogger 二分+最短路★\n2312 坦克大战 spfa最短路本质变形–\u003e广搜★\n2387 Til the Cows Come Home 基础最短路★\n2394 Checking an Alibi 最短路★\n2449 Remmarguts’ Date A*求第K短路★★\n2457 Part Acquisition 最短路 (输出路径)★★\n2472 106 miles to Chicago 乘积最短路(log一下,乘变加)★★\n\n\n2502 Subway\n2570 Fiber Network floyd\n3013 圣诞树\n3037 Skiing\n3072 Robot\n3114 Countries in War 强联通+最短路\n3160 Father Christmas flymouse 强联通+最长路\n3255 Roadblock\n3259 Wormholes (寻找负权回路)\n3268 Silver Cow Part\n3311 Hie with the Pie floyd+状压\n3328 Cliff Climbing\n3439 Server Relocation\n3463 Sightseeing 次短路条数\n3159\n3521 Geometric Map 计算几何+最短路\n3549 GSM phone 计算几何+最短路\n3594 Escort of Dr. Who How\n3613 Cow Relays 经过N条边的最短路 // floyd + 二分矩阵\n3615 Cow Hurdles\n3621 最优比率环\n3635 full tank?\n3660 传递闭包\n3662 Telephone Lines\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d以下是差分约束系列\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n【HDU】\n1384 Intervals\n1529 Cashier Employment\n1531 King\n1534 Schedule Problem\n3440 House Man\n3592 World Exhibition\n3666 THE MATRIX PROBLEM\n\n\n【POJ】\n1201\n1275\n1364\n1716\n2949\n2983\n3159\n3169\n3687\n\n\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d以下是二分匹配系列\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n普通匹配,多重匹配\n\n\n【HDU】\n\n\n1068 Girls and Boys\n1150 \u0026nbsnbsp; Machine Schedule\n1151 Air Raid\n1179 Ollivanders: Makers of Fine Wands since 382 BC.\n1281 棋盘游戏\n1498 50 years, 50 colors\n1507 Uncle Tom’s Inherited Land*\n1528 Card Game Cheater\n1845 Jimmy’s Assignment\n2063 过山车\n2119 Matrix\n2444 The Accomodation of Students\n2768 Cat vs. Dog\n3081 Marriage Match II\n3360 National Treasures\n1045 也可搜索\n1350 最小路径覆盖\n3118 类似二分匹配\n3729\n2389\n1054\n2819 完全匹配\n1668 二分+多重匹配\n3605 多重匹配\n3861 强连通+二分匹配\n2236 无题II\n\n\nhdu3468\nhdu4185 奇偶匹配\n\n\n\n\n\n\n【POJ】\n1087 A Plug for UNIX\n1274 The Perfect Stall\n1469 COURSES\n1486 Sorting Slides 二分图的必须边\n1548 Robots\n1698 Alice’s Chance\n1719 Shooting Contest\n1904 King’s Quest 求二分图所有可能的匹配边\n2060 Taxi Cab Scheme 最小路径覆盖\n2112 Optimal Milking 二分+多重匹配\n2226 Muddy Fields 行列的覆盖\n2239 Selecting Courses\n2289 Jamie’s Contact Groups 二分+多重匹配\n2446 Chessboard\n2536 Gopher II\n2584 T-Shirt Gumbo\n2594 Treasure Exploration 可相交最小路径覆盖\n2672 Hotkeys\n2724 Purifying Machine\n3020 Antenna Placement\n3041 Asteroids 简单行列匹配\n3189 Steady Cow Assignment 二分+多重匹配\n3207 Ikki’s Story IV - Panda’s Trick\n3216 Repairing Company\n3343 Against Mammoths\n3692 Kindergarten\n2771 最大独立集\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d以下是KM算法系列\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n【HDU】\n2255 奔小康赚大钱\n1533 Going Home\n1853 Cyclic Tour\n3488 Tour\n3435 A new Graph Game\n2426 Interesting Housing Problem\n2853 Assignment\n3718 Similarity\n3722 Card Game\n3395 Special Fish\n2282 Chocolate\n2813 One fihgt one\n2448 Mining Station on the Sea\n3315 My Brute\n3523 Image copy detection\n\n\n【POJ】\n2195 Going Home 最小权值匹配\n2400 Supervisor, Supervisee 输出所有最小权匹配\n2516 Minimum Cost 最小权值匹配或最小费用流\n3565 Ants\n3686 The Windy’s 最小权值匹配\n\n\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d以下是最大团\u0026稳定婚姻系列\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n【HDU】\n\n\n1530 Maximum Clique\n1435 Stable Match\n3585 maximum shortest distance 二分+最大团\n1522 Marriage is Stable\n1914 The Stable Marriage Problem\n\n\n【POJ】\n\n\n1129 四色定理 着色问题\n1419 最大独立集\n2989 极大团\n3487 The Stable Marriage Problem 稳定婚姻\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d以下是强双联通系列\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n【HDU】\n强连通:\n1269 迷宫城堡 判断是否是一个强连通\n2767 Proving Equivalences 至少加几条边让整个图变成强连通\n3836 Equivalent Sets 至少加几条边让整个图变成强连通\n1827 Summer Holiday 传递的最小费用\n3072 Intelligence System 传递的最小费用\n3861 The King’s Problem 强连通+二分匹配\n3639 Hawk-and-Chicken 强连通缩点 + 树形dp(累加子节点的总权值)\n3594 Cactus 仙人掌图\n\n\n双连通:\n2242 考研路茫茫——空调教室 双联通缩点+树形DP\n2460 Network 边双连通\n3849 By Recognizing These Guys, We Find Social Networks Useful 双连通求桥\n3896 Greatest TC 双连通\n4005 The war 边双连通\n\n\nLCA:\n2586 How far away ?\n2874 Connections between cities\n3078 Network LCA+排序\n3830 Checkers 二分+LCA\n\n\n【POJ】\n强连通:\n1236 Network of Schools\n2553 The Bottom of a Graph 好题! 找出度为0的集合\n2186 Popular Cows 好题! 找出度为0的,其他分量都指向它的集合\n2375 Cow Ski Area 强连通\n2762 Going from u to v or from v to u? 缩点+拓扑排序\n3160 Father Christmas flymouse 强连通+最短路\n3180 The Cow Prom 判断有几个环, 分量中元素大于1的个数\n3114 Countries in War 强连通+最短路\n3592 Instantaneous Transference 强连通分量+最长路\n1904 King’s Quest 强连通+并查集\n\n\n双连通:\n3694 Network 边双连通 (同hdu2460)\n3177 Redundant Paths 构造边双连通\n3352 Road Construction 构造边双连通\n2942 Knights of the Round Table (点双连通经典题)\n1515 Street Directions (无向图改有向图)\n1438 One-way Traffic (混合图改有向图)\n\n\nLCA:\n1330 Nearest Common Ancestors\n1470 Closest Common Ancestors\n1986 Distance Queries\n3417 Network\n3728 The merchant LCA+并查集,更新询问\n2763 Housewife Wind LCA+树状数组\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d以下是2-SAT系列\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n【HDU】\n3062 Party\n1824 Let’s go home\n3622 Bomb Game\n3715 Go Deeper\n1815 Building roads\n2723 Get Luffy Out\n1816 Get Luffy Out *\n1814 Peaceful Commission\n4115 Eliminate the Conflict\n\n\n\n\n\n\n【POJ】\n2296 Map Labeler\n2723 Get Luffy Out\n2749 Building roads\n3207 Ikki’s Story IV - Panda’s Trick\n3648 Wedding\n3678 Katu Puzzle\n3683 Priest John’s Busiest Day\n3905 Perfect Election\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d以下是欧拉回路系列\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n【HDU】\n1878 欧拉回路 判断\n3018 Ant Trip 一笔画问题\n1116\n2894 兹鼓欧拉回路\n1956\n3472 混合欧拉\n\n\n【POJ】\n2513 欧拉路\n1041 John’s trip 欧拉回路\n1386 Play on Words 单词接龙\n2230 Watchcow 欧拉回路\n2513 Colored Sticks 无向图欧拉路\n2337 Catenyms 欧拉路径\n1392 Ouroboros Snake 兹鼓欧拉回路\n1780 code\n1637 混合欧拉\n\n\n【zoj】\n1992\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d以下是拓扑排序系列\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n【HDU】\n1285 确定比赛名次\n2094 产生冠军\n2647 Reward\n3342 Legal or Not\n1811 Rank of Tetris 拓扑+并查集\n3231 三维拓扑\n\n\n【POJ】\n1094 Sorting It All Out Floyd+拓扑\n2367 Genealogical tree\n3660 Cow Contest\n3687 Labeling Balls 神奇的拓扑\n1128 Frame Stacking DFS版拓扑\n1270 Following Orders 拓扑+回溯\n1420 Spreadsheet 模拟拓扑\n2762 Going from u to v or from v to u? 强连通+拓扑\n3553 Task schedule\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d以下是竞赛图系列\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n竞赛图下的哈密顿问题\n\n\nStrange Country II ZOJ-3332\nTask Sequences POJ-1776\nThe book SGU-122\nTour Route POJ-3780\nTour Route HDOJ-3414\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d以下是网络流系列\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n【HDU】\n\n\n\n\n\n\n1532 Drainage Ditches(基础) [最大流]\n3549 Flow Problem(基础) [最大流]\n3572 Task Schedule [最大流]任务分配,判断满流\n2732 Leapin’ Lizards(难) [最大流]\n3338 Kakuro Extension [最大流][数和]神奇最大流行进列出\n2883 kebab [最大流]判断满流\n3605 Escape [最大流](多重匹配\n3081 Marriage Match II [二分最大流]+并查集\n3277 Marriage Match III [二分最大流]同上,多了拆点\n3416 Marriage Match IV [最大流]最短路+最大流\n2485 Destroying the bus stations [最大流]最短路+最大流\n3468 Treasure Hunting 最大流+最短路\n3551 Hard Problem [最大流]\n3998 Sequence(难) [DP+最大流]最长上升子序列\n3917 Road constructions [最大权闭包]\n3879 Base Station [最大权闭包]\n3061 Battle [最大权闭包]\n3996 Gold Mine [最大权闭包]\n3472 HS BDC [混合欧拉]\nhdu4183 来回走不重复点的网络流.\n————————-\n1533 Going Home(基础) [费用流]\n3488 Tour [费用流]圈\n3435 A new Graph Game [费用流]圈\n1853 Cyclic Tour [费用流]圈\n2686 Matrix [费用流]\n3376 Matrix Again [费用流]\n3667 Transportation [费用流]拆边\n3315 My Brute 费用流\n3395 Special Fish 费用流\n2448 Mining Station on the Sea 费用流\n4067 Random Maze(难) [费用流]\n3947 River Problem(难) [费用流]神奇费用流,流量不等式建图\n3046 Pleasant sheep and big big wolf [最小割]\n1565 方格取数(1) [最小割]\n1569 方格取数(2) [最小割]\n3820 Golden Eggs [最小割]方格加强\n3491 Thieves [最小割]最小点割集\n3657 Game [最小割]最大点权独立集\n3313 Key Vertex [最小割]\n3251 Being a Hero [最小割]\n3157 Crazy Circuits [上下流]\n3002 King of Destruction [全局最小割]\n3691 Nubulsa Expo [全局最小割]\n【POJ】\n1087 A Plug for UNIX 最大流\n1274 The Perfect Stall 最大流\n1325 Machine Schedule 最大流\n1698 Alice’s Chance 最大流\n2239 Selecting Courses 最大流\n2446 Chessboard 最大流 好题啊\n2536 Gopher II 最大流\n2771 Guardian of Decency [最大流]二分匹配最大独立集\n3041 Asteroids 最大流\n2584 T-Shirt Gumbo 最大流\n3189 Steady Cow Assignment(中等) 二分最大流\n1149 PIGS [最大流] 绝对经典的构图题\n1273 Drainage Ditches 最大流\n1459 Power Network(基础) [最大流]\n3281 Dining [最大流]\n2112 Optimal Milking(基础) [二分最大流]\n2289 Jamie’s Contact Groups [二分最大流]\n2391 Ombrophobic Bovines(中等) [二分最大流]\n2455 Secret Milking Machine(基础) [二分最大流]\n3228 Gold Transportation 二分最大流\n2699 The Maximum Number of Strong Kings(较难) [枚举人数 + 最大流]\n3498 March of the Penguins(中等) [最大流]枚举汇点,满足点容量限制的网络流\n2987 Firing(较难) [最大权闭包]\n1637 Sightseeing tour(Crazy) [混合欧拉]\n2135 Farm Tour [费用流] (来回最短路)\n2175 Evacuation Plan(中等) [费用流] 消圈\n2195 Going Home [费用流]\n2516 Minimum Cost [费用流]\n3422 Kaka’s Matrix Travels(中等) [费用流]拆点\n3680 Intervals(较难) [费用流]经典,费用流+离散化\n3686 The Windy’s 费用流\n3762 The Bonus Salary! [费用流]\n1815 Friendship(中等) [最小割]最小点割集\n1966 Cable TV Network(中等) [最小割]最小点割集\n2125 Destroying The Graph(难) [最小割]最小点权覆盖\n3084 Panic Room(中等,好题) [最小割]边连通度\n3204 Ikki’s Story I - Road Reconstruction(基础) [最小割]求关键边\n3308 Paratroopers(较难) [最小割]乘积取对数,最小点权覆盖\n3436 ACM Computer Factory [最小割]收集流,残留搜集找边\n3469 Dual Core CPU(中等) [最小割]收集流\n3921 Destroying the bus stations [最小割]点连通\n2396 Budget(中等) [有源汇的上下界可行流]\n3155 Hard Life(很挑战一题) [最大密度子图]\n2914 Minimum Cut [无向图最小割]\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d以下是dancing links系列\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n1001 Easy Finding POJ-3740\n1002 Power Stations HDOJ-3663\n1003 Treasure Map ZOJ-3209\n1004 Lamp HDOJ-2828\n1005 whosyourdaddy HDOJ-3498\n1006 Bomberman - Just Search! HDOJ-3529\n1007 Square Destroyer POJ-1084\n1008 Matrix HDOJ-2119\n1009 Divisibility HDOJ-3335\n1010 Radar HDOJ-2295\n1011 Fire station HDOJ-3656\n1012 Repair Depots HDOJ-3156\n1013 Dominoes HDOJ-2518\n1014 Street Fighter HDOJ-3957\n1015 Sudoku Killer HDOJ-1426\n1016 Sudoku POJ-2676\n1017 Sudoku POJ-3074\n1018 Sudoku POJ-3076\n1019 Su-Su-Sudoku HDOJ-2780\n1020 Sudoku HDOJ-3111\n1021 Sudoku HDOJ-3909\n1022 Squiggly Sudoku HDOJ-4069\n1023 Triangle War II ZOJ-3038\n1024 A Puzzling Problem HDOJ-1603\n1025 Maximum Clique HDOJ-1530\nhust1017 精确覆盖。\nfzu1686,nuaa1507 重复覆盖。\nhit2199,2882,2959 精确覆盖(数独)。\nSPOJ1771 精确覆盖(N皇后问题)。\npoj3435","threadId":39040,"likeCnt":25,"createTime":1542158650000,"isWorkbook":false,"viewCnt":3641,"openness":2,"fav":false,"id":730,"trustable":false}