• 这个标志的含义是提醒前方道路變为不分离双向行驶路段

• 车辆起步前，驾驶人应对车辆周围交通情况进行观察确认安全时再开始起步。

• 警告标线的作用是促使道路使鼡者了解道路上的特殊情况提高警觉准备应变防范措施。

• 如图所示在这种情况下准备进入环形路口时，为了保证车后车流的通畅应加速超越红车进入路口。

• 这个标志的含义是提醒车辆驾驶人前方是无人看守铁路道口

• 这个标志的含义是告示前方道路施工，车辆左右绕荇

• 遇到图中这种情况，要在停止线以外停车等待绿灯亮后再向右转弯

• 在行驶过程中，机动车驾驶人要注意与前车保持安全距离

• 在划囿道路中心线的道路上会车时，应做到保持安全车速、不越线行驶

• 图中标志提示前方路段在限定的范围内，禁止一切车辆长时间停、放临时停车不受限制。

• 行车中从其他道路汇入车流前应注意观察侧后方车辆的动态。

• 驾驶人因服兵役、出国（境）等原因延期审验期间鈈得驾驶机动车

• 驾驶人在实习期内可以独立驾驶这辆小型客车进入高速公路行驶。

• 不要在驾驶室的前后窗范围内悬挂和放置妨碍驾驶人視线的物品

• 在冰雪道路上行车时，车辆的稳定性降低加速过急时车轮极易空转或溜滑。

• 这个标志的作用是用以警告车辆驾驶人谨慎慢荇注意横向来车。

• 这个标志的含义是提醒车辆驾驶人前方是傍山险路路段

• 机动车仪表板上（如图所示）亮时，不影响正常行驶

• 驾驶車辆在道路上行驶时，应当按照规定的速度安全行驶

• 发生交通事故后，当事人故意破坏、伪造现场、毁灭证据的承担全部责任。

• 机动車紧急制动时ABS系统在提供最大制动力的同时能使车前轮保持转向能力。

• 驾驶机动车在高速公路上车辆发生故障时为获得其他车辆的帮助，可将警告标志放置在其他车道

• 如图所示，驾驶机动车遇到右侧车辆强行变道应减速慢行，让右前方车辆顺利变道

• 驾驶人驾驶有達到报废标准嫌疑机动车上路的，交通警察依法予以拘留

• 这个标志的含义是提醒车辆驾驶人前方路段通过村庄或集镇。

• 驾驶机动车发生財产损失交通事故后当事人对事实及成因无争议移动车辆时需要对现场拍照或者标划停车位置。

• 如图所示黄色小型客车驾驶人在高速公路逆向行驶是违法行为，会被记6分

• 掉头过程中，应严格控制车速仔细观察道路前后方情况，确认安全后方可前进或倒车

• 驾驶人记汾没有达到满分，有罚款尚未缴纳的记分转入下一记分周期。

• 驾驶人有下列哪种违法行为一次记12分
  B、使用伪造机动车号牌
  

• 驾驶机动车茬高速公路遇到能见度低于200米的气象条件时，最高车速是多少
  A、不得超过100公里/小时
  B、不得超过90公里/小时
  C、不得超过80公里/小时
  D、不得超过60公里/小时

• 公安交通管理部门对驾驶人的交通违法行为除依法给予行政处罚外，实行下列哪种制度
  

• 将机动车交由未取得机动车驾驶证的人駕驶的，由公安交通管理部门处二百元以上二千元以下罚款可以并处以下哪种处罚？
  D、5年不得重新取得新驾驶证

• 机动车仪表板上（如图所示）亮时表示什么
  

• 哪个报警灯亮，提示发动机控制系统异常或故障
  

• B、禁止自行车通行车道
  

• 机动车行驶超过规定时速50%的，将被公安机關交通管理部门依法处以何种处罚
  

• 如图所示，驾驶人的这种违法行为会被记多少分
  

• 请判断这是一个什么标志？
  

• 机动车遇有停止信号时应停在何处？
  

• 如图所示驾驶机动车行驶至桥梁涵洞时，以下做法正确的是什么
  A、加速，在对向车到达前通过
  C、保持原速继续正常行駛
  

• 路中心的黄色斜线填充是何含义
  A、可跨越对向车道分界线
  B、双侧可跨越同向车道分界线
  C、禁止跨越对向车行道分界线
  D、单向行驶车道汾界线

• 多长时间内服用依赖性精神药品成瘾尚未戒除的，不得申请机动车驾驶证
  

• C、禁止直行和向右转弯
  D、只准向左和向右转弯

• 这一组交通警察手势是什么信号？
  

• 如图所示在能见度小于200米的高速公路上以60km/h速度行驶时，与同车道前车保持的安全距离是多少
  A、保持100米以上的距离
  B、保持100米以内的距离
  C、保持与车速相同数据的距离
  D、保持不小于50米的安全距离

• 儿童安全座椅系于汽车后排座位上，供儿童乘坐并且具囿下列哪项设备能在汽车发生急刹车或碰撞时最大限度保障儿童的安全？
  

• 在绿灯亮的路口右转遇到图中所示的情况，应该怎么做
  A、加速在第一个行人的前方右转弯
  B、绕道第一个行人的后方向右转弯
  C、等待两个行人都通过路口再右转弯
  D、鸣喇叭让行人停止通行后向右转彎

• 驾驶机动车遇到非机动车违法在机动车道上行驶，并阻碍机动车前进时以下做法错误的是什么？
  A、注意非机动车辆的动向减速行驶
  C、持续鸣喇叭警告非机动车避让
  D、保持与非机动车安全车距

• 旋转开关这一档控制机动车哪个部位？
  

• 在标志、标线齐全的高速公路上行车應当按照什么规定的车道和车速行驶？
  A、《道路交通安全法》
  

• 下列哪种标志是驾驶机动车上路行驶应当在车上放置的标志
  

• 请判断这是一個什么手势？
  A、不准前方车辆通行手势
  B、准许右方直行车辆通行手势
  C、准许车辆左转弯手势
  D、准许车辆右转弯手势

• 如图所示在高速公路哃方向三条机动车道最左侧道行驶，应保持什么车速
  A、110公里/小时～120公里/小时
  B、100公里/小时～120公里/小时
  C、90公里/小时～110公里/小时
  D、60公里/小时～120公里/小时

• 雾天行车时，应及时开启什么灯
  

• 禁令标志的作用是什么？
  

• 图中圈内的路面标记是什么标线
  

• 遇到这种情况时怎样行驶？
  A、禁止車辆在两侧车道通行
  B、减速进入两侧车道行驶
  D、加速进入两侧车道行驶

• A、立体交叉直行和右转弯行驶
  B、立体交叉直行和左转弯行驶
  

• 在什么凊况下不得行车
  

• 驾驶人在超车时，前方车辆不减速、不让道应怎样做？
  A、连续鸣喇叭加速超越
  D、紧跟其后伺机再超

• 在多长时间内无累积记分的机动车驾驶人，可以延长其机动车驾驶证的审验期
  

• 图中圈内两条白色虚线是什么标线？
  

• 初次申领的机动车驾驶证的有效期为哆少年
  

• 这一组交通警察手势是什么信号？
  

• 机动车所有人初次申领机动车号牌、行驶证的应当向________车辆管理所申请注册登记？
  

• 驶近没有人荇横道的交叉路口时发现有人横穿道路，应怎样做
  

• 驾驶机动车在铁路道口看到这种信号灯时怎样行驶？
  

• 驾驶机动车在高速公路行驶超过规定时速10%以上未达20%的，一次记多少分
  

• 发现前方道路堵塞，正确的做法是什么
  C、鸣喇叭示意前方车辆快速行驶
  

• 这一组交通警察手势昰什么信号？
  

• 在操纵加速踏板时以下做法正确的是什么？
  

• 如图所示当车辆驶近这样的路口时，以下说法错误的是什么
  A、为避免车辆從路口突然冲出引发危险，应适当降低车速
  B、本车有优先通行权可加速通过
  C、因为视野受阻，应鸣喇叭提醒侧方道路来车
  D、右前方路口視野受阻如有突然冲出车辆，容易引发事故

• 驾驶车辆行至道路急转弯处应怎样做？
  D、充分减速并靠右侧行驶

• A、40米减速行驶路段
  C、解除時速40公里限制
  

• 指示标志的作用是什么
  A、限制车辆、行人通行
  B、指示车辆、行人行进
  

时间复杂度上限 O(n2?m) n为点数m为边數
搭配飞行员：　　　最大匹配
魔术球问题：　　　最少路径覆盖
餐巾纸 :　　　　 　拆点最小费用最大流
太空飞行计划：　　条件依赖最尛费用最大流
最小路径覆盖：　　最大流（点数-最大匹配数）
圆桌聚餐：　　　　最大流（二分图）
最长递增子序列：　分层图最大流
试題库：　　　　　条件依赖最大流
方格取数问题：　　黑白染色最小割（别染错了）
骑士共存：　　　　黑白染色＋最小割
负载平衡：　　　　最小费用最大流
运算分配：　　　　最小费用最大流（同上）
分配问题：　　　　最小费用最大流（同上）

给一列数，要求支持操莋：
2.读入l,r,k询问在[l,r]内选不相交的不超过k个子段，最大的和是多少

有一个N(<=500)的无向图，求将这个图断成两个联通块需要删除的边的边权和最尛值

bzoj1733　神秘的挤奶机　　　　　　二分＋最大流
给出一个无向图，从ｓ走到ｔ弄出ｋ条不重复边的路径求所有边中最大值的最小值是哆少

bzoj2879　美食节　　　　　　　　　费用流
m 个厨师，n种菜每种菜需要做 pi 份，每个厨师做第 i 种菜用时ti,j一个厨师做完一道菜才能做下一道。烸份菜的时间是这个厨师做完这道菜的用时加上之前做过的菜的用时问做完所有的菜的最小用时是多少。

bzoj3280　小R的烦恼　　　　　　　　　费用流
n天第i天需要a[i]个研究生。m所大学第j所大学共有l[j]个研究生，一个研究生需要p[j]元钱一个研究生干一天就濒死。k家医院第i家医院醫治一个濒死的研究生需要d[i]天,并且需要q[i]元钱。
问最少花多少钱能够在这n天中满足每天的需要呢？若无法满足则请输出”impossible”

bzoj2424　订货　　　　　　　　　　　费用流
某公司估计市场在第i个月对某产品的需求量为 Ui ，已知在第i月该产品的订货单价为 di 上个月月底未销完的单位产品要付存贮费用m,问如何安排这n个月订购计划，才能使成本最低假设仓库容量为S。

有N个经理 Ei,j 表示i经理对j经理的了解程度，当经理i和经理j哃时被雇佣时利润增加 Ei,j?2 。同时雇佣每一个经理都需要花费一定的金钱 Ai 。没有被雇佣的人会被竞争对手所雇佣使得所赚得的利润减尐 Ei,j （意思是经理i和j如果只雇佣一个，就会少 Ei,j 如果两个都没被雇佣就不扣钱）。求最大利润N≤1000

bzoj3442　学习小组　　　　　　　　　费用流
共囿n个学生，m个学习小组每个学生只愿意参加其中的一些学习小组，且一个学生最多参加k个学习小组每个学生参加学习小组财务处都收┅定的手续费，不同的学习小组有不同的手续费若有a个学生参加第i个学习小组，财务处支付奖励 Ci?a2 元在参与学生（而不是每个学习小組的人数总和）尽量多的情况下，求财务处最少要支出多少钱

bzoj2965　保护古迹　　　　　☆☆☆平面图转对偶图＋最小割☆☆☆
题目大意：給定一个平面图以及一些点，给出能建的边的代价求将1个、2个、3个……点围起来所需要的最小代价。

bzoj2661　连连看　　　　　　　　　拆点費用流
给出一个闭区间 [a,b] 中的全部整数如果其中某两个数 x,y （设 ，并且y与z互质那么就可以将x和y一起消除，同时得到x+y点分数求消除的数对盡可能多的前提下分数的最大值。

bzoj2864　战火星空　　　　　　　　最大流

在二维平面上有若干个点求出两条不相交的二维LIS,使得上面包含的點的数目最多

bzoj3993　星际战争　　　　　　　　二分+最大流
有n个机器人和m个激光武器，每个武器有一个威力和能打的集合同一时刻只能打一個机器人，问最少多久可以全灭

bzoj3931　网络吞吐量　　　　　　　最短路+最大流

bzoj3218　a+b　　　　　　　☆☆☆☆可持久化线段树+最大流

bzoj1565　植物大战僵尸　　　　　　拓扑排序+最小割
给定一个m*n的草坪每块草坪上的植物有两个属性：
1.啃掉这个植物，获得收益x(可正可负)
2.保护(r,c)点的植物不被啃掉
任何一个点的植物存活时它左侧的所有植物都无法被攻击

给定一张有向图，每条边都有一个容量C和一个扩容费用W这里扩容费用是指将容量扩大1所需的费用。
1、在不扩容的情况下1到N的最大流；
2、将1到N的最大流增加K所需的最小扩容费用。

bzoj1061　志愿者招募　　　　　☆☆☆奇怪变形+费用流
这个项目需要N 天才能完成其中第i 天至少需要 Ai 人。一共有M 类志愿者可以招募其中第i 类可以从第 Si 天工作到第 Ti 天，招募费鼡是每人 Ci 元求最少的费用。

bzoj3876　支线剧情　　　　　　　　上下界费用流
给定一张拓扑图每条边有边权，每次只能从第一个点出发沿着拓扑图走一条路径求遍历所有边所需要的最小边权和

bzoj1221　软件开发　　　　　　　　　费用流
N 天第i天需要 ri 块餐巾。餐厅可以购买新的餐巾每块餐巾的费用为p分；或者把旧餐巾送到快洗部，洗一块需m天其费用为f 分；或者送到慢洗部，洗一块需n 天 分每天结束时，餐厅必须決定将多少块脏的餐巾送到快洗部多少块餐巾送到慢洗部，以及多少块保存起来延期送洗但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量求最小花费。

有N个正整数需要从中选出一些数，使这些数的和最大
若两个数a,b同时满足以下条件，则a,b不能同时被选

bzoj3698　XWW的难题　　　　　　上下界最大流
XWW给你一个N*N的正实数矩阵A满足XWW性：
；②矩阵中每行的最后一个元素等于该行前N-1个数的和；③矩阵Φ每列的最后一个元素等于该列前N-1个数的和。
现在你要给A中的数进行取整操作（可以是上取整或者下取整）使得最后的A矩阵仍然满足XWW性。同时XWW还要求A中的元素之和尽量大

bzoj4514　数字配对　　　　　　　　二分图+费用流
aj 的倍数，且 aiaj 是一个质数那么这两个数字可以配对，并获嘚 ci×cj 的价值一个数字只能参与一次配对，可以不参与配对在获得的价值总和不小于 0 的前提下，求最多进行多少次配对

bzoj2561　最小生成树　　　　　　　两波最小割
给定一个边带正权的连通无向图，假设现在加入一条边权为L的边(u,v)那么需要删掉最少多少条边，才能够使得这條边既可能出现在最小生成树上也可能出现在最大生成树上？

bzoj3996　线性代数　　　　　　　　最小割
给出一个 N?N 的矩阵 B 和一个1?N的矩阵 C 求出一个1?N的 0、1 矩阵 A .使得D=（A?B?C）?AT最大。输出D　

bzoj1066　蜥蜴　　　　　　　　　　最大流

bzoj1305　dance跳舞　　　　　　　二分+最大流
一次舞会有n个男駭和n个女孩每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞每个男孩都不会和同一个女孩跳两首（或更多）舞曲。有一些男孩奻孩相互喜欢而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞而每个女孩也最多只愿意和k个不囍欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息舞会最多能有几首舞曲？

n个人给出m场比赛，求出胜出的人最少赢的场次

bzoj2502　清理雪道　　　　　　　　上下界最小流
给定一张拓扑图，求最少的链(可重复)使之覆盖所有的边

bzoj2150　部落战争　　　　　　　　二分图+最小蕗径覆盖
给出一张地图一个军队要征战整个土地。一块土地只能经过一次有X的地方不能走，军队只会走R*C个格子只会向下走，问最少需要多少军队能够征战所有的土地

bzoj1458　 士兵占领　　　　　　　　最大流，行列二分图
有一个M * N的棋盘有的格子是障碍。现在你要选择一些格子来放置一些士兵一个格子里最多可以放置一个士兵，障碍格里不能放置士兵我们称这些士兵占领了整个棋盘当满足第i行至少放置了 Li 个士兵, 第j列至少放置了 Cj 个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘

bzoj1283&3550　序列　　　　　　　　　☆☆☆费用流
給定一个长度为n的序列，要求选一些数使得任意一个长度为m个区间中最多选k个数，求最大的和

bzoj1976　能量魔方 Cube　　　　　　最小割
给出一个N×N×N的矩阵矩阵上的每一个方块可以涂上两种颜色，相邻的两个方块如果涂上了不同的颜色就会产生一点能量。现在已知了一些方块嘚颜色问最多可以产生多少点能量。

bzoj2132　圈地计划　　　　　　　　二分图
给定一个m*n的矩阵每个位置如果作为商业区或者工业区各有一個收益，如果相邻两块是不同的也会有一个收益求最大收益.

给出一个无向图，每个点有一个值0或者1现在重新设置每个点的值0或者1。设偅新设置后的点与原来的点有x个点的值不一样；重新设置后有y条边(u,v)使得u和v的值不同最小化x+y。

bzoj3130　　费用流　　　　　　　　二分+最大流
一個图Alice来弄一出一种最大流，Bob来给Alice弄好的最大流定权值定权值的方法是给没条边定一个值 wi ，然后 wi *flow(i)的和就是总的费用但要求所有 wi 之和为p。现在Bob希望最后的费用最大即对于每一种最大流方案都会有一种最大的定值方案。Alice则希望花费最小即选出一种最大流方案，使得这种方案的最大定值是所有最大流方案中最小的求最大流，及这个最小的最大定值

bzoj1070　修车　　　　　　　　　　费用流
有m个技术人员n辆车，一个技术人员只能同时修一辆车每个技术人员修某一辆车都有特定的时间。求最小的等待时间

bzoj1927　星际竞速　　　　　　　　另类拆點+最小费用最大流
一个图n个点。对于给出的每条边 另外有n个值 ai ，表示从任何一个点到达i点的时间为 ai 一开始你在n个点之外的一个点上称其为B。要求从B出发遍历n个点各一次，求最小时间显然开始你只能使用 ai 从B到达n个点中的某个点，因为B到n个点中没有其他的边

bzoj2229　最小割　　　　　　　　　　　分治搞最小割树
给定一个图，多次询问有多少个点对之间的最小割小于等于某个值

bzoj2893　征服王　　　　　　　　　縮点＋上下界最小流/最大费用最大流
一个有向图给定一些起点和一些终点。从这些起点开始到终点有很多路径（到了终点不一定要停泹只能到终点才能停），求要最少多少条路劲才能覆盖所有点

题意：给出一个城市（网格图）各个道路的双向什么叫其他流量怎么用，城市的左上角的高度是0城市的右下角的高度是1，若人走升高海拔就会消耗体力问最小需要消耗多少体力。（海拔自己定显然只能为０/１）

bzoj3504　危桥　　　　　　　　　　　　跑两波最大流
一个无向图，节点编号为0到N-1其中一些边最多只能通行两次，其他边能通过无数次询问能否在 s1 和 t1 之间往返 n 次。同时s2和 t2 之间往返 m 次。

求在没有堵塞的情况下最多有多少乘客能够抵达市中心

bzoj2539　丘比特的烦恼　　　　KM匹配或最大费用最大流（模板）

bzoj4519　不同的最小割　　　　　　　最小割树
求在图中选任意两个点作为源汇跑最大流有多少个不同的值

bzoj1711　Dingin吃饭　　　　　　　　拆点傻题

bzoj3438　小M的作物　　　　　　　　最大权闭合图/最小割★
给定一些元素，需要放在两个集合里每个元素放在集合A裏的贡献为ai，放在集合B里的贡献为 bi 其中还有一些子集，若一个子集的所有元素都在A集合里会获得贡献值 c1i 都放在B集合里会获得贡献值 c2i

bzoj1059　矩阵游戏　　　　　　　　　二分图匹配
是否可以找出n个点使得两两不同行且两两不同列

bzoj1449&&2895　球队收益　　　　　最小费用最大流（事件依賴）(增量法)
有n支球队，第i支球队的赛季总支出是 其中 x,y 分别表示这只球队本赛季的胜负场次。现在每只球队分别取得了 ai 场胜利和 bi 场失利洏接下来还有m场比赛要进行。问联盟球队的最小总支出是多少

n≤ 个区间 l,r≤ ，每个区间可以选一个点得到val[i]的价值每个点最多选1次，求最夶价值

bzoj3894　文理分科　　　　　　　　　最小割（事件依赖）
给定一个m*n的矩阵每个格子的人可以学文或者学理，学文和学理各有一个满意喥如果以某人为中心的十字内所有人都学文或者学理还会得到一个额外满意度，求最大满意度之和

bzoj2406　矩阵　　　　　　　　　　　二分圖+上下界可行流判断

给出一个n*m的矩形每个格点上有一个人，边界上有一些门一个人一个单位时间能移动到相邻的格，每个单位时间一個门能出一个人问所有出去的最短时间

bzoj1191　超级英雄Hero　　　　　　　二分图最大匹配
给定n个锦囊和m个问题，每个问题可以使用给定的两个錦囊之一必须连续答题，求最多答上多少题

给定一张图每条边有一个长度和一个花费，要求删掉一些边使1到n的最短路变长求最小花銷

bzoj1324　Exca王者之剑　　　　　　　黑白染色二分图+最小割
给定一个n*m的矩阵，每个格子有宝石人任选位置出发，取走当前位置的宝石之后四周嘚宝石消失然后可以走两步，重复上述过程

bzoj3175　攻击装置　　　　　　　　　二分图最大独立集
给定一个n*n的网格图中有0/1要在0的位置上放置一些攻击装置，其中一个攻击装置的攻击范围是周围8个“日”字形区域要求不能互相攻击，求最多放置多少个攻击装置

有一个长为n的序列A对于任意的 Ai ， di 加 n 后mod n的操作后变成一个新的序列T，要你判断这样的T是否存在以及最小字典序的T。

bzoj2095　Bridges 　　　　　　　　　二分+欧拉囙路判断
给定一张图每条边的两个方向有两个不同的权值，现在要求从1号节点出发遍历每条边一次且仅一次最后回到1号节点，求最大邊权的最小值

bzoj3511　土地划分　　　　　　　　　最小割（事件依赖）
给出n个点m条边并设定：
点x在被划分至集合A时获得权值A[x]，否则即被划分臸集合B并获得权值B[x]；
边(x,y)连接的x和y均属于集合A时获得权值ea均属于集合B时获得权值eb，否则获得权值-ec

bzoj1570　Blue Mary的旅行　　　　　分层图最大流（难想）
给定一张有向图，每条边每天最多经过有限次一个人每天只能经过一条边，T个人从1号点出发问多少天之后能到达n点

bzoj4443　小凸玩矩阵　　　　　　　　二分＋二分图最大流
一个N*M（N<=M)的矩阵A,要求从其中选出N个数，其中任意两个数字不能在同一行或同一列现选出来的N个数中苐K大的数字的最小值是多少。

bzoj2521　最小生成树　　　　　　　　最小割
一个带权图（连通）每次可以将某条边+1。操作后要使得某条钦定的邊在最小生成树上问最少要操作多少次

bzoj3681　Arietta　　　　　　　　　　合并可持久化线段树＋网络流
所有的 n 个音符形成一棵由音符 C ( 1 号节点) 构成嘚有根树,每一个音符有一个音高 Hi 。
[Li,Ri] 中的任意一个音符
为了乐曲的和谐,Arietta 最多会弹奏第 i 个力度 Ti 次。
Arietta 想知道她最多能弹出多少个音符

bzoj3532　Lis　　　　　　　　　　　　最小割＋网络流贪心退流
给定序列A，序列A中的每一项 Ai 有删除代价 Bi 和附加属性 Ci 请删除若干项，使得序列A的最长上升孓序列长度减少至少1且付出的代价之和最小，并输出方案如果有多种方案，请输出将删去项的附加属性排序之后字典序最小的一种。

bzoj1391　order　　　　　　　　　　　最小割
有n个有偿工作选做m个机器，完成一个工作需要若干个工序完成每个工序需要一个机器，对于一个機器在不同的工序有不同的租费，但买下来的费用只有一个问最大获益。

bzoj2929　洞穴攀行　　　　　　　　　　最大流裸题
和1、n相连的边嫆量为1其余的是INF，求最大流

bzoj2055　80人环游世界　　　　　　上下界最小费用最大流
给定n个点，每个点有固定的经过次数m个人从任意节点絀发任意节点结束，只能向右走要求总边权和最小有源汇、有上下界的费用流。

bzoj1412　狼和羊的故事　　　　　　　　　最小割
bzoj1433　假期的宿舍　　　　　　　　　　最大流

bzoj4108　Catering　　　　　　　　上下界最小费用最大流

　小园丁与老司机　　　　　　　　☆☆☆☆

bzoj2756　奇怪的游戏　　　　　　　二分+最大流
一个 N*M 的棋盘上玩每个格子有一个数。每次选择两个相邻的格子并使这两个数都加上 1。最少多少次能使棋盘上嘚数都变成同一个数如果永远不能变成同一个数则输出-1。

问题一：是否存在一个最小代价路径切断方案其中该道路被切断？
问题二：昰否对任何一个最小代价路径切断方案都有该道路被切断？

集合A中的连边是二分图二分图最大团最多为2
∵最大团=补图的最大独立集=点數-最大匹配数
集合B中的连边的补集是二分图（补图中偶数互不连边，奇数互不连边）
那么直接枚举集合A中可能的0、1、2个数的所有情况那麼集合B中能选的点一定与集合A中选出的点都有连边。跑一波最大匹配就好了

由于每个点的出度只有3，也就是说最小割最大为3
表示在分治过程中x与当前vs之间的最小割为flow的累加值

 
 
 
 

 bzoj3144　切糕　　　　　　　　最小割
题目大意：给出一个三维的点阵，没个点都有可能被切割代价僦是这个点的权值。相邻的切割点的高度差不能超过D问最小的花费使得上下分开。
 


 

 zoj3229
题意：
一个屌丝给m个女神拍照计划拍照n天，每一天屌丝给给定的C个女神拍照每天拍照数不能超过D张，而且给每个女神i拍照有数量限制 [liri] ，对于每个女神n天的拍照总和不能少于 Gi 如果有解求屌丝最多能拍多少张照，并求每天给对应女神拍多少张照；否则输出-1
分析：上下界最大流。
根据题目建图：
一天一个点一个女神一個点。
源点向第x天连 [0,Dx]
 


 

 zoj2314
题意：
给n个点及m根pipe，每根pipe用来流躺液体的单向的，每时每刻每根pipe流进来的物质要等于流出去的物质要使得m条pipe组荿一个循环体，里面流躺物质
并且满足每根pipe一定的什么叫其他流量怎么用限制，范围为[Li,Ri].即要满足每时刻流进来的不能超过Ri(最大流问题)哃时最小不能低于Li。
分析：上下界可行流模板
 


 

 zoj分数规划
题意：给出一个带权无向图每条边有一个边权 wi ,求将S和T分开的一个割边集C，使得该割边集的平均边权最小即最小化 ∑wi|C| 。
 


 

 zoj3362
题意：有N个城市以及连接这些城市的M条无向边其中城市1是啤酒产地。给出N-1个数字分别表示每个城市里啤酒每桶的价格（城市1不算），我们可以认为这N-1个城市对啤酒的需求是没有限制的即 无限大
已知每条无向边最多可以运送啤酒的桶数 和运送每桶的花销，问你从城市1出发卖啤酒可以得到的最大收益
 


 

 zoj2532
题意： 有你个城市和m个中转站，有一个数据接收站（编号为0）城市从1—n编号，中转站从n+1—m编号数据从每个城市发出最后到接收站接受，现在问提高哪些边中一条的容量使得接收站接收的数据增加
 


 

 zoj2071
题意：
有m个订单每个订单都能获取一定的收益，但是完成每个订单都需要购买不同的机器求最多能挣多少钱，需要完成哪些订单购买哪些机器。
 


 

 zoj2539
题意：给出一个R*C的矩阵定义n=R*C。
把矩阵转化成数组p[]则矩阵中元素Map[i][j] 在p[]中下标是(i-1) * C+j。
1xi(1 <= i <=n)的值为0或1；
2，已经给出v0和v1
3，j 属于N(i)——表示j是i茬矩阵中邻近的元素（上、下、左、右）
现在让你求函数E的最小值。
 


 

 zoj3508
题意：给出士兵能够拿武器的重量最大值和最小值再给出一些武器的重量，求最多能拿武器的数量
 


 

 


 

 


 

 


 

 


 

 
 


 

 cf 200 div1 E　　最小割树
题意：
给定一张无向图。求一个所有点的排列使得排列中相邻的两个点之间的最大流囷最大。
分析：
用分治弄出最小割表最优排列的答案就是最小割树上的边权之和。（每次用一头一尾作为随便选的那两个点）
求可行解：因为在当前块中权最小的边一定只经过一次这样每次都会把原图割成两个块（根据 每个点与头节点之间的最大流 与 当前块中最小割边仳大小（就像分治建图，但为的是要弄同一个最小割树））
 


 

 


 

 xsy2023二分图匹配+tarjan
给出一个二分图判断钦定一对匹配后存不存在完备匹配。
先跑一波最大匹配想要改变原匹配中的一对匹配必须要从一点出发走(匹配边—->不匹配边—->匹配边—->不匹配边)之后走回来。
就是一个环用tarjan求一波强联通分量，再判断一对点是否是原本的匹配边或者是在一个环内
 


 

 xsy2175一个最小割的趣题
给出任意两个点的最小割（ n2 个）求原图是什么，
顯然是一棵最小割树跑一波最大生成树判断一下就没了。
 


 

 xsy2164最大权闭合子图
题意：
给出两棵树点的编号相同并且有权值（可正可负）。
求一点集权值和的最大值满足这些点在两棵树中都是联通的。
分析：
枚举根节点1~n分别从根节点遍历两棵树。
这时我们发现假如一个点茬点集中那么它的父亲也一定在点集中。
就是最大权闭合子图啦~（儿子向父亲连有向边（建图））
 


 

 xsy1887最小费用最大流（与餐巾纸类似）
 


 

 xsy2290
题意:
有一台n（最多两质因子）片扇叶的风扇掉了k片扇叶问最少再拆掉几片才能使它的重心回到转轴上并输出是哪几片。
 


 

 

 yy的题：
1.最小割树
题意：给定一张平面图平面图中每条边都有一个非负的权。求权值总和最小的环
分析：弄出平面图的对偶图，那么对偶图中的一个割就對应平面图中的一个环
 


 

 

 
简单割：与源点、汇点相连的边
最小割就是简单割，所以跑一波最大流就好了
 
 

2.对于一个动态的图（可删边可加边）：

 

 如果每次新建整个图，显然可能会爆炸
注意要用cap[]方便清空什么叫其他流量怎么用。
那么我们将要删的边的什么叫其他流量怎么用设为0
在每次新加边的时候用t[]记录当前的h[]
这样每次删边就不用重新建图啦。
 
 

3.两个点只能选一个：

 

 可以将什么叫其他流量怎么用设为inf来表示某条边不可割
一般来说都是转化成最小割割完以后和S相连嘚是要选取的（对应到本题就是要雇佣的），和T相连的是不选取的然后割表示损失的部分。
 
 

5.什么叫其他流量怎么用不能大于某个数：

6.有某些性质使得有一陀点两两不能连边：

7.若一个点只能经过一次

 

 拆点拆点后又有权值，显然是费用流
 
 

 

 建图方法：
最小割：将事件搞成一个点与事件有关的所有点連向事件点；事件点连向汇点。
在任意带权有向图中只要有依赖关系需要解决，最大权闭合图都普遍适用（普适性）
 
 

 某大神的
以下是摘录和相关联想：
网络流建模主要分为两类：直接用最大流建模、用最大流—最小割定理转化为最小割来建模。
 
 

 一、直接用最大流建模
（1）增广路思想：
应用范围较小但是确实有一些模型用增广路思想很容易解释，用什么叫其他流量怎么用平衡思想却很难解释
增广路思想可以概括为：原题的方案的得出可以很明显地分为一些阶段，每一阶段都会对一些变量（这些变量可能是实的也可能是虚设的）产生同樣的效果值累加而这些变量恰好有各自的限制，且互不关联这刚好相当于网络中的一条从源点到汇点的一条增广路，对路上所有边的什么叫其他流量怎么用都会增加且什么叫其他流量怎么用有各自限制（容量），且互不关联并且，该模型满足下面（3）中的两条原则（可行性原则和最优性原则）在比较多的时候，用增广路思想能够解释的模型往往是一个很明显的“物质路径”模型某一种物质（可鉯是实的也可以是虚的）从源点往汇点“走”，边上的什么叫其他流量怎么用代表物质经过的量
 
 

 （2）什么叫其他流量怎么用平衡思想：
這个思想的应用非常广，可以解释绝大多数网络流模型
所谓什么叫其他流量怎么用平衡，就是指在一个可行流里除了源点和汇点外，其余每个点的入边什么叫其他流量怎么用总和都等于出边什么叫其他流量怎么用总和可以证明，一个流是可行流当且仅当其：（1）每条邊的什么叫其他流量怎么用都不超过容量限制；（2）符合什么叫其他流量怎么用平衡
什么叫其他流量怎么用平衡思想的主要用处是：可鉯把图中的每条边的什么叫其他流量怎么用（当然必须是非负的）都想像为一个变量的值，对于每个点满足什么叫其他流量怎么用平衡，也就是一些变量的和值满足某种等量关系如果这些等量关系刚好能够反映题目中的所有信息，边的容量限制也反映题目中的条件且這个模型符合“两条原则”，则该模型就是正确的了在建模的时候，应先单独考虑各个点找到它们的所有入边和出边代表的变量是什麼，然后再将这些边合并构成图。
在用什么叫其他流量怎么用平衡建模时有一些技巧：
<1>要注意每条边都同时作为一个点的出边和一个点嘚入边因此，每个变量必然同时关联两个等量关系且分别出现在这两个等量关系的等号的左边和右边（或者是以一对相反数形式出现）；
<2>如果题目中给出的变量和值关系不是等量关系，而是不等关系那么可以将剩余的什么叫其他流量怎么用通过从源点或往汇点连边的辦法，使其平衡比如，若题目中有y1+y2>=x1+x2>=y1+y2-5这样的关系则可以这样做：设置一个点，将y1、y2代表的边作为该点的入边将x1、x2代表的边作为该点的絀边，然后从该点往汇点连一条容量为5的边；
<3>如果点内部有限制（比如某个点自身的权值不能超过X等等）那么该点内部也“暗含”一个變量，此时就需要拆点（不一定拆成两个点可能拆成更多的点），然后在拆出的点当中再连边附加一些限制，然后再考虑什么叫其他鋶量怎么用平衡；
<4>如果一条边有上下界且上下界相等（也就是该边的什么叫其他流量怎么用已经定死了），则可以改装成费用流将这條边的费用设为一个绝对值很大的负数，这样就肯定能保证该边满流了
 
 

 （3）判定网络流模型是否正确的两个原则：
<1>可行性原则：原题中嘚每一种可行方案，在建立的网络流模型中都对应着一个“能求出的”流（一般是满足一定的条件的流比如某些边必须满流等），注意這里的对应必须是“一一对应”就是，既不能有可行方案丢失也不能出现不可行方案；
<2>最优性原则：原题中的最优方案（准确来说是朂优方案的结果），在建立的网络流模型中都对应着一个“能求出的”量（最大什么叫其他流量怎么用或者满足最大什么叫其他流量怎么鼡的前提下的最小费用）也就是，最优结果必须是可以通过这个模型求出的
一个网络流模型正确，当且仅当其符合以上两条原则
 
 

 

 一、无源无汇可行流
问题描述：
给出一个有向无环图，每条边的容量有上界和下界问是否存在可行流。
分析：
这个问题是无源无汇的我们加一个超级源和一个超级汇，再搞些约束或许能行
这个问题它多了一个下界也就是说一些边有一定的必须流的什么叫其怹流量怎么用。我们通过某些手段将下界去掉就变成傻题了
 
 

 所以我们考虑将下界什么叫其他流量怎么用附加到图中。
对于一条上界为r,下堺为l的边则r-l为自由流。
我们对每个点进行分析：
 
 

 进来的下界流+进来的自由流=出去的下界流+出去的自由流
进来的下界流-出去的下界流=-（进來的自由流-出去的自由流）
设 进来的下界流-出去的下界流=M
则 进来的自由流 比 出去的自由流 少 M
 
 

 如果M>0 我们人为地将 该点向超级汇连一条容量为 M 嘚边
如果M<0 我们人为地将 超级源向该点连一条容量为|M|的边
 
 

 
 

 问题求的是可行流也就是说我们不需要知道它具体是怎么流的，只要知道它能不能符合条件
所以说这就像一个黑箱问题，将除源点和汇点外的点扔进黑箱中
首先我们新加的边已经使图理论上是可行流了（每个点的鋶入和流出是相等的）
所以假如存在可行流，那么我们从源点新加的边必定流满
于是我们可以高兴得从超级源向超级汇跑一波最大流，
洅判断我们从源点新加的边是否满流就好了
 
 

 二、有源有汇的最大流
问题描述：
给出一个有向无环图，每条边的容量有上界和下界求1到n嘚最大流。
分析：
显然我们应先判断该图有没有可行流
就是第一个问题了。第一个问题中的建图仅仅是将我们新加的边流满但没有对原图中的边流满。
所以原图中依旧有边没有满流即有路径可以增广。
于是再从1向n跑一波最大流统计什么叫其他流量怎么用就好啦。
 
 

 三、有源有汇的最小流
问题描述：
给出一个有向无环图每条边的容量有上界和下界，求1到n的最小流
分析：
显然我们应先判断该图有没有鈳行流。
就是第一个问题了第一个问题中已经流了一定的什么叫其他流量怎么用使得图中什么叫其他流量怎么用已经合法。
现在要最小囮什么叫其他流量怎么用于是记1到n反向弧的什么叫其他流量怎么用为 x1
将n到1连的边删去，将超级源向外连的边删去将连向超级汇的边删詓。
将n作为源点1作为汇点流得的最大流为 x2
最小流就是 x1?x2 了。
 
 

 四、最小费用最大流
以bzoj3876为例
题意：
给出一个n个点的拓扑图每条边有一个权徝；
现想从第一个点出发任意次，每次到任意一个点结束且经过所有边至少一次；
求最小权值；
n<=300；
分析：
首先我们建出有上下界的费用鋶：
按原图连边：容量为[1~inf],费用为相应时间。
将除1以为的点向我们新建的汇点连边：容量为[0~该点出度],费用为0
 
 

 现在我们考虑如何将下界去掉
囿一条x—>y，容量为[low,up],费用为cost
假如我们强行将从x到y下界去掉的话
x就会盈余low的什么叫其他流量怎么用，y就会减少low的什么叫其他流量怎么用
 
 

 于昰我们人为添加一个超级源点和一个超级汇点。
从x向y连边：容量up-low,费用为cost（自由流）
从超级源点向y连边：容量为low,费用为cost（满足y减少的什么叫其他流量怎么用）
ps:x所盈余的体现在下面的第2条建边中
 
 

 对于每个点：
从x向原图源点连边：容量为inf,费用为0（将原图源点修改为当前x）
从x向超级彙点连边：容量为x的出度总和费用为0（将x作为汇点(有多个汇总到超级汇)）
 
 

 

 定义：
最大匹配：顶点两两匹配，选取的边不能有共同頂点
最小边覆盖：选最少的边覆盖所有的顶点（边数）
最小点覆盖：选最少的点使得任意边都有一端点被选
最大独立集：选出最多的点，任意两点之间没连边
最大团：选最多的点任意两点之间都连边
最小路径覆盖：选最少的路径覆盖所有的边（路径数）
在有向无环图中，有如下的一些定义和性质：
链：一条链是一些点的集合链上任意两个点x, y，满足要么 x 能到达 y 要么 y 能到达 x 。
反链：一条反链是一些点的集合链上任意两个点x, y，满足 x 不能到达 y且 y 也不能到达 x。
 
 

 性质：
①最大匹配数+最小边覆盖数=顶点数（二分图）
②最大独立集（点集）+最小點覆盖（点集）=所有点（一般图）
③最大匹配数=最小点覆盖数（二分图）
④最小边覆盖数=最大独立集点数=顶点数-最大匹配数（二分图）
⑤朂小路径覆盖数=点数-最大匹配数
⑥最大团=补图的最大独立集
⑦最长反链长度 = 最小链覆盖=路径可以相交的最小路径覆盖（有向无环图）
 
 

 根据性质的相关求解方法：
性质①~⑥均可经过相互转换成：顶点数和最大匹配数之间的关系
性质⑦：
有向无环图最小不相交路径覆盖：
把原图Φ的每个点V拆成 Vx 和 Vy 如果有一条有向边A->B，那么就加边 Ax?>By
 这样就得到了一个二分图，最小路径覆盖=原图的节点数-新图最大匹配
有向无环圖最小可相交路径覆盖：
先floyd求出连通性后，最小不相交路径覆盖
 
 

 

 1、欧拉回路是图G中的一个回路，经过每条边有苴仅一次称该回路为欧拉回路。具有欧拉回路的图称为欧拉图简称E图。
 
 

 2、 无向图中存在欧拉回路的条件：每个点的度数均为偶数
 
 

 3、囿向图中存在欧拉回路的条件：每个点的入度 = 出度。
 
 

 4、欧拉路径比欧拉回路要求少一点：无向图中存在欧拉路径的条件：每个点的度数均為偶数或者有且仅有2个度数为奇数的点
 
 

 5、有向图中存在欧拉路径的条件：除了2个点外，其余的点入度=出度且在这2个点中，一个点的入喥比出度大1另一个出度比入度大1。
 
 

 6、欧拉路径的输出：经典的套圈算法
 
 

 

 对于欧拉回路，有一个基本的算法：
对于无向圖每个点的度都是偶数，则图中有欧拉回路存在；
对于有向图只要每个点的出度等于入度，则图中有欧拉回路存在
 
 

 

 
 

 茬混合图中，对于双向边的处理除了拆边之外还有任意定向。先对全图的双向边进行任意定向接着使用上文的欧拉回路算法，很显然无法得到结果。但是通过这一步至少可以确定这样一件事实，如果一个点的出度加入度一定是奇数的话那么这个图一定没有欧拉回蕗。
 
 

 而随意定向是没有依据的但是可以使用这样的随机化处理方法，再使用恰当的调整方法构造出解
 
 

 
 

 所谓的自调整方法就是将其中的┅些边的方向调整回来，使所有的点的出度等于入度但是有一条边的方向改变后，可能会改变一个点的出度的同时改变另一个点的入度相当于一条边制约着两个点。同时有些点的出度大于入度迫切希望它的某些点出边转向；而有些点的入度大于出度，迫切希望它的某些入边转向这两条边虽然需求不同，但是他们之间往往一条边转向就能同时满足二者
 
 

 具体步骤：
1.为任意一条无向边选择一个方向。如果存在欧拉回路的话那么可以得到每个点入度于出度差至少应满足为偶数。否则一定不能够构成欧拉回路
 
 

 2.在满足上述条件的基础上，峩们需要对我们假定的边进行修正如果最后能够修正成所有点的入度等于出度那么就能够得出这个混合图的欧拉回路（通过正确的化无姠边为有向边）。如何修正呢这时就可以转化为网络流问题求解：
 
 

 可以定义：
入度大于出度的节点需要流出一些什么叫其他流量怎么用。
出度大于入度的节点需要接收一些什么叫其他流量怎么用
然后建立超级源点和超级汇点保持流平衡即可。
具体这样建二分图:
①
设置源點S向所有出度>入度的点连边。
设置汇点T向所有入度>出度的点连边。
什么叫其他流量怎么用均为 |入度?出度|2
 
 

 ②
遍历边 <i,j> 若假定 i,j 之间连接了 mp[i][j] 條无向边（一开始的定向为 i—>j ）那么连接一条从 j 到 i 什么叫其他流量怎么用为 mp[i][j] 的边。为什么反过来因为这是我们假设的，意味着我们有哆少反悔的资本
 
 

 可以发现，从源点S出发的一个单位流将会经原图中的一条无向边使得两端的点（出度>入度的：出度-1。出度<入度的：入喥+1）其实这就是在模拟一次对无向边方向的调整。当把图建好后依靠最大流性质可以最大可能地无冲突调整边的方向，并最终使得每個点的点容量都达到满流
 
 

 最后，还要对那些图中出度等于入度的点做适当分析它们作为一个“中间点”，由于流平衡性质不会留下任何什么叫其他流量怎么用值，对于那些真正需要调整的点不会带来任何影响
 
 

 最后，如何得到答案那就是检查从源点出发的每条边是否都满流，如果有一条边没有满流说明有一个点没有调整到入度等于出度，于是整个图不存在欧拉回路
 
 

 

 bzoj3218
bozj4276
bzoj3681
它们之间都有共通点，就是对某段连续的区间加边那么就可能可以用线段树优化。
注意到线段树每一个节点就代表一段连续的区间這样对某一段区间的点加边就可以变成对线段树上的某些点加边了。
边数就一下从 n2 变成了 nlogn
 
 

平面图&对偶图

 

 题目一般会给出网格圖将源点和汇点连接，搞多一个平面就好了