冬令营预备网络流与匹配

网络流与匹配网络流、匹配的基本概念网络流、匹配的基本算法建模举例纲要网络流

定义

定义

定义

基本算法I增广路算法：不断在残留网络中寻找增广路进行增广，直到找不到增广路时算法结束。例如：深度优先搜索广度优先搜索（Edmonds-Karp）标号法（SAP）（间隙优化）基本算法II

基本算法II层次图中的网络流算法：不同于之前的增广路算法，这类算法每次可以查出很多条增广路。主要方法是通过构建网络层次图并在其中寻找增广路来实现。例如：MPLADinicMPM基本算法III

基本算法III预流推进算法详见算法导论及moonancient的代码。基本算法IV二分图匹配N个人，M件任务。每个人能胜任M件任务中的若干件。已知每件任务只需要一个人来完成，每个人也只能完成一件任务。问，是否存在一种安排使得：每个人都有任务每个任务都有人去做同时满足上面两个条件简单例子

基本算法I

基本算法II

定义

基本算法III

基本算法IV

基本算法V建模举例FJ在修建挤奶机，但是不想被牛发现。在修建过程中，他要去挤奶机T次。农场是N<=200个顶点的无向图，有<=40000条道路（允许重边），FJ想去挤奶机T次（从顶点1出发，且不需要考虑返回），每次的每个道路都不能重复。安排这些路径，使得经过的所有单个道路中最长的一条最短。POJ2455SecretMilkingMachine有N<=1000头奶牛和B<=20个牛棚。每个牛棚都有一定的容量。每个奶牛都给每个牛棚排了顺序，最喜欢哪个，其次是哪个……求一种可行的分配方案，使得所有奶牛选择牛棚的名次差最小（即使他们都选了最不喜欢的也可以）。POJ3189SteadyCowAssignmentF<=200个挡雨棚，每个挡雨棚有各自的容量。有些挡雨棚之间有路径相连，路径可以认为无限宽并且通过需要一定的时间。一开始一些挡雨棚附近有一定数量的奶牛，问至少需要多少时间，才能使得每一头奶牛都找到合适的挡雨棚。POJ2391OmbrophobicBovines一场比赛由N<=30个代表队参与。每个队伍都要和其他队伍比赛一次。胜一场比赛得1分，输则得0分。现在已经决出一些场次的胜负，问哪些队伍可能夺冠？联赛对于一个N行、M列的0-1矩阵，规定在第i行中1的个数恰为Ri，在第j列中1的个数恰为Cj个，每一行、每一列最多可以有一个格子指定为0。问是否存在一种满足条件的0-1矩阵。N,M<=1000，每个测试点最多10组数据2006年江苏省选拔赛矩阵游戏IBM公司要运送一批货物从A星球到B星球。有些星球之间有双向的传送门，但是每天每个传送门至多只能使用一次。问至少需要多少天，才能把K个货物全部送到。N<=50,K<=50,M<=200。POJ1895BringThemThere有N个学生要去参观M个学校，要求每个学生至多只能参观一个学校（也可以一个学校都不参观）。分别给出每个学生愿意参观哪些学校，求一个满足每个学校至少有两个学生参观的方案，或输出符合条件的方案不存在。限制：M≤N≤200。SGU242Student’sMorning给出一个含N个顶点的有向无环图G。用尽量少的不相交路径覆盖G的所有顶点，即每个顶点严格属于一条路径。允许路径的长度为0，即只含一个顶点。最小路径覆盖给出一个带权二分图，其中X部和Y部各有N个顶点。求一个完备匹配，满足匹配边中权值最大的边的权值尽量小。最小最大匹配国王有N个儿子，每个儿子都喜欢一些女孩。现在每个儿子要娶一个女孩（一个女孩只能嫁给国王的一个儿子）。每个儿子有一个权值Ai，如果他娶的是自己喜欢的女孩，则满意度为Ai，否则为0。求一个分配方案，使得所有儿子的满意度之和最大。限制：N≤400。SGU210BelovedSons有T种馅料，每个匹萨都会正好包含其中的K种。现在有C头奶牛。每头牛都有一个喜欢的馅料的集合，如果一个匹萨含有的所有馅料都属于这个集合