Part 8.7-8.9.2 图论

## Part 8.7 图的连通性相关 > 利用 Tarjan 算法，我们可以解决很多与图的连通性相关的问题。 - [P3387 【模板】缩点](https://www.luogu.com.cn/problem/P3387) - [P3388 【模板】割点（割顶）](https://www.luogu.com.cn/problem/P3388) - [P2341 [HAOI2006]受欢迎的牛](https://www.luogu.com.cn/problem/P2341) - [P2863 [USACO06JAN]The Cow Prom](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) ## Part 8.8 二分图 > 二分图上的不少问题都可以转化成网络流解决，当然也有独特的其他方法。 - [P3386 【模板】二分图匹配](https://www.luogu.com.cn/problem/P3386) - [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](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) ## Part 8.9 网络流 > 网络流是图论中一个重要的分支，很多题目都可以通过建立网络流的模型来解决。 ### Part 8.9.1 最大流 > 最大流，即求网络中最大的流量。 - [P3376 【模板】网络最大流](https://www.luogu.com.cn/problem/P3376) - [P4722 【模板】最大流 加强版 / 预流推进](https://www.luogu.com.cn/problem/P4722) - [P2065 [TJOI2011]卡片](https://www.luogu.com.cn/problem/P2065) - [P2763 试题库问题](https://www.luogu.com.cn/problem/P2763) - [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) - [P3749 [六省联考2017]寿司餐厅](https://www.luogu.com.cn/problem/P3749) ### Part 8.9.2 最小割 > 最小割，即求一个边权最小的边集，使得源点和汇点不再连通。 > > 可以证明，**最大流=最小割**。 - [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]善意的投票](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)