能力提升综合题单Part8 图论3

#### Part 8.9.3 费用流 > 在网络流中给边加上一个参数——费用，就出现了费用流。 - [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) - [P3356 火星探险问题](https://www.luogu.com.cn/problem/P3356) - [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) #### Part 8.9.4 上下界网络流 > 在网络流问题中给每条边的流量增加一个下界，就有了上下界网络流。 - [P3980 [NOI2008]志愿者招募](https://www.luogu.com.cn/problem/P3980) - [P4043 [AHOI2014/JSOI2014]支线剧情](https://www.luogu.com.cn/problem/P4043) - [P4553 80人环游世界](https://www.luogu.com.cn/problem/P4553) - [P4843 清理雪道](https://www.luogu.com.cn/problem/P4843) ### Part 8.10 2-SAT > k-SAT 问题的目标是对一些布尔变量赋值，满足限定的条件。 > > 在 k-SAT 问题中，2-SAT 问题属于较为容易解决的一类。 - [P4782 【模板】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) ### Part 8.11 点分治 > 点分治是一种可以高效统计树上路径信息的算法。 - [P3806 【模板】点分治1](https://www.luogu.com.cn/problem/P3806) - [P2634 [国家集训队]聪聪可可](https://www.luogu.com.cn/problem/P2634) - [P2664 树上游戏](https://www.luogu.com.cn/problem/P2664) - [P3714 [BJOI2017]树的难题](https://www.luogu.com.cn/problem/P3714) - [P4149 [IOI2011]Race](https://www.luogu.com.cn/problem/P4149) - [P3241 [HNOI2015]开店](https://www.luogu.com.cn/problem/P3241) - [P4075 [SDOI2016]模式字符串](https://www.luogu.com.cn/problem/P4075) - [P4183 [USACO18JAN]Cow at Large P](https://www.luogu.com.cn/problem/P4183) - [P4292 [WC2010]重建计划](https://www.luogu.com.cn/problem/P4292) - [P5306 [COCI2019]Transport](https://www.luogu.com.cn/problem/P5306) ### Part 8.12 虚树 > 将一些无用的点从树上删去，从而达到降低树的规模的效果。 - [P2495 [SDOI2011]消耗战](https://www.luogu.com.cn/problem/P2495) - [P3233 [HNOI2014]世界树](https://www.luogu.com.cn/problem/P3233) - [P5360 [SDOI2019]世界地图](https://www.luogu.com.cn/problem/P5360) - [P5439 【XR-2】永恒](https://www.luogu.com.cn/problem/P5439) ### Part 8.13 矩阵树定理 > 矩阵树定理可以解决图的生成树计数问题。 - [P4111 [HEOI2015]小Z的房间](https://www.luogu.com.cn/problem/P4111) - [P2144 [FJOI2007]轮状病毒](https://www.luogu.com.cn/problem/P2144) - [P3317 [SDOI2014]重建](https://www.luogu.com.cn/problem/P3317) - [P4208 [JSOI2008]最小生成树计数](https://www.luogu.com.cn/problem/P4208)