第十章
题单介绍
# [返回目录](https://www.luogu.com.cn/training/441063)
## 10.1 图的存储
## 10.2 拓扑排序
### 例10.1 [Following Orders](http://poj.org/problem?id=1270)
#### 课后习题:
[P1113 杂务](https://www.luogu.com.cn/problem/P1113)
[P1347 排序](https://www.luogu.com.cn/problem/P1347)
[P1685 游览](https://www.luogu.com.cn/problem/P1685)
[P3243 [HNOI2015] 菜肴制作](https://www.luogu.com.cn/problem/P3243)
[P1983 [NOIP2013 普及组] 车站分级](https://www.luogu.com.cn/problem/P1983)
[P1038 [NOIP2003 提高组] 神经网络](https://www.luogu.com.cn/problem/P1038)
[P4934 礼物](https://www.luogu.com.cn/problem/P4934)
[P4017 最大食物链计数](https://www.luogu.com.cn/problem/P4017)
[P2597 [ZJOI2012] 灾难](https://www.luogu.com.cn/problem/P2597)
[poj 1094 Sorting It All Out](http://poj.org/problem?id=1094)
[poj 2367 Genealogical tree](http://poj.org/problem?id=2367)
[poj 2585 Window Pains](http://poj.org/problem?id=2585)
[poj 1128 Frame Stacking](http://poj.org/problem?id=1128)
[hdu 1285 确定比赛名次](https://acm.hdu.edu.cn/showproblem.php?pid=1285)
[hdu 3342 Legal or Not](https://acm.hdu.edu.cn/showproblem.php?pid=3342)
[hdu 2647 Reward](https://acm.hdu.edu.cn/showproblem.php?pid=2647)
[hdu 4857 逃生](https://acm.hdu.edu.cn/showproblem.php?pid=4857)
[hdu 1811 Rank of Tetris](https://acm.hdu.edu.cn/showproblem.php?pid=1811)
## 10.3 欧拉路
### 例10.2 [The Necklace](https://www.luogu.com.cn/problem/UVA10054)
### 例10.3 [Code](http://poj.org/problem?id=1780)
#### 课后习题:
[P1341 无序字母对](https://www.luogu.com.cn/problem/P1341)
[P1333 瑞瑞的木棍](https://www.luogu.com.cn/problem/P1333)
[P2731 [USACO3.3] 骑马修栅栏 Riding the Fences](https://www.luogu.com.cn/problem/P2731)
[P1127 词链](https://www.luogu.com.cn/problem/P1127)
[P6066 [USACO05JAN] Watchcow S](https://www.luogu.com.cn/problem/P6066)
[P6628 [省选联考 2020 B 卷] 丁香之路](https://www.luogu.com.cn/problem/P6628)
[hdu 1878 欧拉回路](https://acm.hdu.edu.cn/showproblem.php?pid=1878)
[hdu 1116 Play on Words](https://acm.hdu.edu.cn/showproblem.php?pid=1116)
[hdu 5883 The Best Path](https://acm.hdu.edu.cn/showproblem.php?pid=5883)
[poj 1300 Door Man](http://poj.org/problem?id=1300)
[poj 1041 John's trip](http://poj.org/problem?id=1041)
[poj 1386 Play on Words](http://poj.org/problem?id=1386)
[poj 2337 Catenyms](http://poj.org/problem?id=2337)
[poj 2330 Advanced ASCII Cubes](http://poj.org/problem?id=2330)
[poj 2513 Colored Sticks](http://poj.org/problem?id=2513)
[poj 1392 Ouroboros Snake](http://poj.org/problem?id=1392)
[poj 3018 Giftbox](http://poj.org/problem?id=3018)
[poj 1780 Code](http://poj.org/problem?id=1780)
## 10.4 无向图的连通性
### 例10.4 [Network](http://poj.org/problem?id=1144)
### 例10.5 [Road Construction](http://poj.org/problem?id=3352)
## 10.5 有向图的连通性
### 例10.6 [Polynomial Problem](https://acm.hdu.edu.cn/showproblem.php?pid=1296)
#### 课后习题:
[P3387 【模板】缩点](https://www.luogu.com.cn/problem/P3387)
[P3388 【模板】割点（割顶）](https://www.luogu.com.cn/problem/P3388)
[P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G](https://www.luogu.com.cn/problem/P2341)
[P2863 [USACO06JAN] The Cow Prom S](https://www.luogu.com.cn/problem/P2863)
[P2746 [USACO5.3] 校园网Network of Schools](https://www.luogu.com.cn/problem/P2746)
[P1407 [国家集训队] 稳定婚姻](https://www.luogu.com.cn/problem/P1407)
[P2272 [ZJOI2007] 最大半连通子图](https://www.luogu.com.cn/problem/P2272)
[P3225 [HNOI2012] 矿场搭建](https://www.luogu.com.cn/problem/P3225)
[P5058 [ZJOI2004] 嗅探器](https://www.luogu.com.cn/problem/P5058)
[P2515 [HAOI2010] 软件安装](https://www.luogu.com.cn/problem/P2515)
[poj 2942 Knights of the Round Table](http://poj.org/problem?id=2942)
[poj 2186 Popular Cows](http://poj.org/problem?id=2186)
[poj 1523 SPF](http://poj.org/problem?id=1523)
[poj 3352 Road Construction](http://poj.org/problem?id=3352)
[poj 3177 Redundant Paths](http://poj.org/problem?id=3177)
[hdu 3394 Railway](https://acm.hdu.edu.cn/showproblem.php?pid=3394)
[hdu 3749 Financial Crisis](https://acm.hdu.edu.cn/showproblem.php?pid=3749)
[hdu 2460 Network](https://acm.hdu.edu.cn/showproblem.php?pid=2460)
[hdu 4587 TWO NODES](https://acm.hdu.edu.cn/showproblem.php?pid=4587)
[hdu 1827 Summer Holiday](https://acm.hdu.edu.cn/showproblem.php?pid=1827)
[hdu 3072 Intelligence System](https://acm.hdu.edu.cn/showproblem.php?pid=3072)
[hdu 3836 Equivalent Sets](https://acm.hdu.edu.cn/showproblem.php?pid=3836)
[hdu 3639 Hawk-and-Chicken](https://acm.hdu.edu.cn/showproblem.php?pid=3639)
[hdu 3861 The King’s Problem](https://acm.hdu.edu.cn/showproblem.php?pid=3861)
[hdu 1540 Tunnel Warfare](https://acm.hdu.edu.cn/showproblem.php?pid=1540)
## 10.6 基环树
### 例10.7 [[ZJOI2008] 骑士](https://www.luogu.com.cn/problem/P2607)
#### 课后习题:
[P5049 [NOIP2018 提高组] 旅行 加强版](https://www.luogu.com.cn/problem/P5049)
[P4381 [IOI2008] Island](https://www.luogu.com.cn/problem/P4381)
[P1399 [NOI2013] 快餐店](https://www.luogu.com.cn/problem/P1399)
[P1453 城市环路](https://www.luogu.com.cn/problem/P1453)
## 10.7 2-SAT
### 例10.8 [【模板】2-SAT](https://www.luogu.com.cn/problem/P4782)
#### 课后习题:
[P4171 [JSOI2010] 满汉全席](https://www.luogu.com.cn/problem/P4171)
[P3825 [NOI2017] 游戏](https://www.luogu.com.cn/problem/P3825)
[P5332 [JSOI2019] 精准预测](https://www.luogu.com.cn/problem/P5332)
[hdu 3062 Party](https://acm.hdu.edu.cn/showproblem.php?pid=3062)
[hdu 1824 Let's go home](https://acm.hdu.edu.cn/showproblem.php?pid=1824)
[hdu 4115 Eliminate the Conflict](https://acm.hdu.edu.cn/showproblem.php?pid=4115)
[hdu 4421 Bit Magic](https://acm.hdu.edu.cn/showproblem.php?pid=4421)
## 10.8 最短路径
### 例10.9 [蓝桥公园](https://www.lanqiao.cn/problems/1121/learning/)
### 例10.10 [Minimum Transport Cost](https://acm.hdu.edu.cn/showproblem.php?pid=1385)
### 例10.11 [灾后重建](https://www.luogu.com.cn/problem/P1119)
### 例10.12 [跑路](https://www.luogu.com.cn/problem/P1613)
### 例10.13 [Rank](https://acm.hdu.edu.cn/showproblem.php?pid=1704)
### 例10.14 [[USACO06NOV] Roadblocks G](https://www.luogu.com.cn/problem/P2865) 或者[Roadblocks](http://poj.org/problem?id=3255)
### 例10.15 [最短路](https://acm.hdu.edu.cn/showproblem.php?pid=2544)
### 例10.16 [[USACO07DEC] Sightseeing Cows G](https://www.luogu.com.cn/problem/P2868) 或者 [Sightseeing Cows](http://poj.org/problem?id=3621)
### 例10.17 [【模板】差分约束](https://www.luogu.com.cn/problem/P5960)
#### 课后习题:
[P1730 最小密度路径](https://www.luogu.com.cn/problem/P1730)
[P2419 [USACO08JAN] Cow Contest S](https://www.luogu.com.cn/problem/P2419)
[P3385 【模板】负环](https://www.luogu.com.cn/problem/P3385)
[P1993 小 K 的农场](https://www.luogu.com.cn/problem/P1993)
[P4779 【模板】单源最短路径（标准版）](https://www.luogu.com.cn/problem/P4779)
[P3371 【模板】单源最短路径（弱化版）](https://www.luogu.com.cn/problem/P3371)
[P5905 【模板】全源最短路（Johnson）](https://www.luogu.com.cn/problem/P5905)
[P1144 最短路计数](https://www.luogu.com.cn/problem/P1144)
[P1462 通往奥格瑞玛的道路](https://www.luogu.com.cn/problem/P1462)
[P1522 [USACO2.4] 牛的旅行 Cow Tours](https://www.luogu.com.cn/problem/P1522)
[P1266 速度限制](https://www.luogu.com.cn/problem/P1266)
[P4568 [JLOI2011] 飞行路线](https://www.luogu.com.cn/problem/P4568)
[P3238 [HNOI2014] 道路堵塞](https://www.luogu.com.cn/problem/P3238)
[P5304 [GXOI/GZOI2019] 旅行者](https://www.luogu.com.cn/problem/P5304)
[P3275 [SCOI2011] 糖果](https://www.luogu.com.cn/problem/P3275)
[P2294 [HNOI2005] 狡猾的商人](https://www.luogu.com.cn/problem/P2294)
[P4926 [1007] 倍杀测量者](https://www.luogu.com.cn/problem/P4926)
[P5590 赛车游戏](https://www.luogu.com.cn/problem/P5590)
[hdu 1599 find the mincost route](https://acm.hdu.edu.cn/showproblem.php?pid=1599)
[hdu 1217 Arbitrage](https://acm.hdu.edu.cn/showproblem.php?pid=1217)
[hdu 3631 Shortest Path](https://acm.hdu.edu.cn/showproblem.php?pid=3631)
[hdu 1596 find the safest road](https://acm.hdu.edu.cn/showproblem.php?pid=1596)
[hdu 1869 六度分离](https://acm.hdu.edu.cn/showproblem.php?pid=1869)
[hdu 3986 Harry Potter and the Final Battle](https://acm.hdu.edu.cn/showproblem.php?pid=3986)
[hdu 3832 Earth Hour](https://acm.hdu.edu.cn/showproblem.php?pid=3832)
[poj 2391 Ombrophobic Bovines](http://poj.org/problem?id=2391)
[poj 3275 Ranking the Cows](http://poj.org/problem?id=3275)
[poj 3463 Sightseeing](http://poj.org/problem?id=3463)
[poj 1860 Currency Exchange](http://poj.org/problem?id=1860)
[poj 3259 Wormholes](http://poj.org/problem?id=3259)
[poj 1062 昂贵的聘礼](http://poj.org/problem?id=1062)
[poj 2253 Frogger](http://poj.org/problem?id=2253)
[poj 1125 Stockbroker Grapevine](http://poj.org/problem?id=1125)
[poj 2240 Arbitrage](http://poj.org/problem?id=2240)
[poj 3621 Sightseeing Cows](http://poj.org/problem?id=3621)
[poj 3635 Full Tank?](http://poj.org/problem?id=3635)
## 10.9 最小生成树
### 例10.18 [【模板】最小生成树](https://www.luogu.com.cn/problem/P3366)
### 例10.19 [[USACO01OPEN] Earthquake](https://www.luogu.com.cn/problem/P4951)
#### 课后习题:
[hdu 4081 Qin Shi Huang's National Road System](https://acm.hdu.edu.cn/showproblem.php?pid=4081)
[hdu 4126 Genghis Khan the Conqueror](https://acm.hdu.edu.cn/showproblem.php?pid=4126)
[hdu 4756 Install Air Conditioning](https://acm.hdu.edu.cn/showproblem.php?pid=4756)
[hdu 4750 Count The Pairs](https://acm.hdu.edu.cn/showproblem.php?pid=4750)
[hdu 3938 Portal](https://acm.hdu.edu.cn/showproblem.php?pid=3938)
[hdu 5627 Clarke and MST](https://acm.hdu.edu.cn/showproblem.php?pid=5627)
[hdu 6187 Destroy Walls](https://acm.hdu.edu.cn/showproblem.php?pid=6187)
[poj 1789 Truck History](http://poj.org/problem?id=1789)
[poj 2485 Highways](http://poj.org/problem?id=2485)
[poj 1258 Agri-Net](http://poj.org/problem?id=1258)
[poj 3026 Borg Maze](http://poj.org/problem?id=3026)
[poj 1797 Heavy Transportation](http://poj.org/problem?id=1797)
[poj 2377 Bad Cowtractors](http://poj.org/problem?id=2377)
[poj 2728 Desert King](http://poj.org/problem?id=2728)
[P4180 [BJWC2010] 严格次小生成树](https://www.luogu.com.cn/problem/P4180)
[P3366 【模板】最小生成树](https://www.luogu.com.cn/problem/P3366)
[P4180 [BJWC2010] 严格次小生成树](https://www.luogu.com.cn/problem/P4180)
[P2872 [USACO07DEC] Building Roads S](https://www.luogu.com.cn/problem/P2872)
[P1991 无线通讯网](https://www.luogu.com.cn/problem/P1991)
[P1967 [NOIP2013 提高组] 货车运输](https://www.luogu.com.cn/problem/P1967)
[P4047 [JSOI2010] 部落划分](https://www.luogu.com.cn/problem/P4047)
[P2121 拆地毯](https://www.luogu.com.cn/problem/P2121)
[P1967 [NOIP2013 提高组] 货车运输](https://www.luogu.com.cn/problem/P1967)
## 10.10 最大流
### 例10.20 [【模板】网络最大流](https://www.luogu.com.cn/problem/P3376)
#### 课后习题:
[P3376 【模板】网络最大流](https://www.luogu.com.cn/problem/P3376)
[P2472 [SCOI2007] 蜥蜴](https://www.luogu.com.cn/problem/P2472)
[P2754 [CTSC1999] 家园 / 星际转移问题](https://www.luogu.com.cn/problem/P2754)
[P2765 魔术球问题](https://www.luogu.com.cn/problem/P2765)
[P2766 最长不下降子序列问题](https://www.luogu.com.cn/problem/P2766)
[P2805 [NOI2009] 植物大战僵尸](https://www.luogu.com.cn/problem/P2805)
[poj 1459 Power Network](http://poj.org/problem?id=1459)
[poj 3436 ACM Computer Factory](http://poj.org/problem?id=3436)
[hdu 3549 Flow Problem](https://acm.hdu.edu.cn/showproblem.php?pid=3549)
[hdu 4280 Island Transport](https://acm.hdu.edu.cn/showproblem.php?pid=4280)
[hdu 3472 HS BDC](https://acm.hdu.edu.cn/showproblem.php?pid=3472)
## 10.11 二分图
### 例10.21 [【模板】二分图最大匹配](https://www.luogu.com.cn/problem/P3386) 或者 [过山车](https://acm.hdu.edu.cn/showproblem.php?pid=2063)
#### 课后习题:
[P2071 座位安排](https://www.luogu.com.cn/problem/P2071)
[P2756 飞行员配对方案问题](https://www.luogu.com.cn/problem/P2756)
[P1129 [ZJOI2007] 矩阵游戏](https://www.luogu.com.cn/problem/P1129)
[P1559 运动员最佳匹配问题](https://www.luogu.com.cn/problem/P1559)
[P2423 [HEOI2012] 朋友圈](https://www.luogu.com.cn/problem/P2423)
[P2764 最小路径覆盖问题](https://www.luogu.com.cn/problem/P2764)
[P2825 [HEOI2016/TJOI2016] 游戏](https://www.luogu.com.cn/problem/P2825)
[P3033 [USACO11NOV] Cow Steeplechase G](https://www.luogu.com.cn/problem/P3033)
[P3731 [HAOI2017] 新型城市化](https://www.luogu.com.cn/problem/P3731)
[P4014 分配问题](https://www.luogu.com.cn/problem/P4014)
[P4617 [COCI2017-2018#5] Planinarenje](https://www.luogu.com.cn/problem/P4617)
[P2065 [TJOI2011] 卡片](https://www.luogu.com.cn/problem/P2065)
[P2763 试题库问题](https://www.luogu.com.cn/problem/P2763)
## 10.12 最小割
#### 课后习题:
[P1344 [USACO4.4] 追查坏牛奶 Pollutant Control](https://www.luogu.com.cn/problem/P1344)
[P1345 [USACO5.4] 奶牛的电信Telecowmunication](https://www.luogu.com.cn/problem/P1345)
[P2057 [SHOI2007] 善意的投票 / [JLOI2010] 冠军调查](https://www.luogu.com.cn/problem/P2057)
[P2598 [ZJOI2009] 狼和羊的故事](https://www.luogu.com.cn/problem/P2598)
[P2774 方格取数问题](https://www.luogu.com.cn/problem/P2774)
[P4126 [AHOI2009] 最小割](https://www.luogu.com.cn/problem/P4126)
[P5039 [SHOI2010] 最小生成树](https://www.luogu.com.cn/problem/P5039)
[P3749 [六省联考 2017] 寿司餐厅](https://www.luogu.com.cn/problem/P3749)
[P4897 【模板】最小割树（Gomory-Hu Tree）](https://www.luogu.com.cn/problem/P4897)
[P4001 [ICPC-Beijing 2006] 狼抓兔子](https://www.luogu.com.cn/problem/P4001)
## 10.13 费用流
### 例10.22 [Farm Tour](http://poj.org/problem?id=2135)
#### 课后习题:
[P3381 【模板】最小费用最大流](https://www.luogu.com.cn/problem/P3381)
[P4016 负载平衡问题](https://www.luogu.com.cn/problem/P4016)
[P4452 [国家集训队] 航班安排](https://www.luogu.com.cn/problem/P4452)
[P2045 方格取数加强版](https://www.luogu.com.cn/problem/P2045)
[P2050 [NOI2012] 美食节](https://www.luogu.com.cn/problem/P2050)
[P2053 [SCOI2007] 修车](https://www.luogu.com.cn/problem/P2053)
[P2604 [ZJOI2010] 网络扩容](https://www.luogu.com.cn/problem/P2604)
[P2770 航空路线问题](https://www.luogu.com.cn/problem/P2770)
[P3159 [CQOI2012] 交换棋子](https://www.luogu.com.cn/problem/P3159)
[P3358 最长k可重区间集问题](https://www.luogu.com.cn/problem/P3358)
[P4013 数字梯形问题](https://www.luogu.com.cn/problem/P4013)
[P4015 运输问题](https://www.luogu.com.cn/problem/P4015)
[P5331 [SNOI2019] 通信](https://www.luogu.com.cn/problem/P5331)
[P3705 [SDOI2017] 新生舞会](https://www.luogu.com.cn/problem/P3705)