EK + Dinic 最大流算法理解 网络流常见问题 最大流:我对残留网的理解： 原本网络中不存在流,为了求出最大流.人为的给出一条任意大小流从 源点出发经过一些边到达汇点.且流的大小最后被限制成 经过的边中 容量最小的边,但是流具有守恒性,不可能凭空产生？？？,所以又要从汇点流回去,所以形成了残留网 最大流算法的图解.以及残留网的图, Ford-Fulkerson (方法) 是一类计算网络流的最大流的贪心算法。 之所以称之为“ 2019-10-06 算法 Edmonds-Karp算法 Dinic算法
最大独立集个数模板 + 最大团计数模板 并没有看懂求最大团个数的算法原理???,已知看到最好的解释最大团blog POJ 2989 最大团计数模板 R集合是 最大团已经加入的点 P集合是 可能加入的点,且与R集合所有的点存在边(????) 还是不太明白X集合的作用 12345678910111213141516171819202122232425262728293031323334353637383940414243444546 2019-10-04 算法 模板 遗留问题
POJ 2400 KM+建图 POJ 2400 题意 n个部门n个员工,每个部门雇佣一个员工,部门希望雇佣每个员工的希望值不同,员工希望被雇佣的部门的希望值也不同, 求使得所有人希望值之和最大,输出最优匹配结果,若有多种,输出所有 思路(借鉴大佬) 题目数据与描述不一样,先给出的每个员工的对部门的希望值,然后才是每个部门的首选项, 将左部分作为部门,右部分作为员工,边权为各自希望值之和, 用KM求出最大的希望值之和 2019-10-03 算法 KM
POJ 2516 KM+建图 POJ 2516 题意: n个店主,m个供货商(仓库),k种商品 给出n个店主的k种商品的需求,m个仓库存放k种商品的个数,和对于每种商品$k_i$来说从$m_i$运送到$n_i$的运费 求最小花费, 如果商品不足则输出-1 思路: 分k次计算：每个商品分别求最小花费,然后加和，建立二分图后首先判断商品数量是否足够给店主.**然后裸KM()** 存数据+建图 shop[i][k]存第i个店 2019-10-03 算法 KM
POJ 3686 KM+建图 POJ 3686 题意 n个订单,m个工厂,第i 个订单在第j个工厂生产时间为g[i][j],工厂同一时间只能生产一个订单,但可以连续处理不同订单,如果都在一个工厂生产.即订单a生产完后才能生产b订单，b订单要等待a订单生产 求处理所有订单的最少时间？输出平均时间 思路(借鉴大神) 将每个工厂分为n个点,每个点代表第k个处理的商品,T=t1+(t1+t2)+(t1+t2+t3)+...等价于 2019-10-03 算法 KM算法
KM算法学习 (二分图带权最大匹配) 计算 二分图带权最大匹配的2种方法: 费用流 / KMKM算法学习 使用局限性:只能在带权最大匹配是完备匹配的图中使用 完备匹配: G=<V1,V2,E>为二分图,$|V_1| < |V_2|$,$M$为$G$中的一个最大匹配数,且$|M|= |V_1|$,则称$M$为$V_1$到$V_2$的完备匹配 完美匹配:当$|V_1| = |V_2|$,若$|V_1|<|V_ 2019-10-02 算法 KM算法
POJ 2226 思维二分图 POJ 2226 背景： 此题在 POJ 3041基础上 需要将连续的点看做一个点 建议先做POJ 3041 题意 给出nxm的网格.有空地.和泥泞*.*求最少要用多少 (宽度为1的可伸长的木板) 覆盖所有的点** 思路 因为木板长度可以任意伸长.所以无论是 行还是列,只要*连续就可以看成一个二分图中的点 还是将行作为二分图的左部.列作为二分图的右部分.先求出原图每个点分别在左部分的编号和 2019-10-02 算法
POJ 3041 思维二分图 POJ 3041 题意 给出nxn的图有m个行星(点).弹药每次能消灭一行或一列上的所有行星(点).问最少需要几次能消灭所有的行星(点)? 思路 将样例数据横坐标x作为二分图左部分的一个点.纵坐标y作为二分图右部分的一个点.坐标(x,y)表示为二分图左部分的x点到右部分的y点的边.画出这样的一个二分图: 求消灭所有行星也就是 画出来的二分图的所有点需要被覆盖. 每次消灭一行或一列 等 2019-10-02 算法
POJ 2594 最小路径覆盖(点重复) POJ 2594 二分图性质: 最小路径(点)覆盖(路径不相交) = N - 最大匹配题意: 在有向无环图.求最小路径(点)覆盖(路径相交的点可重复) 思路 假设一条路径经过u->p->v,另一条x->p->y.路径相交于点p,于是添加一条x->y或者u->v的边 能够使得2条路径不相交 进一步: 将有向图中所有的间接点.通过添加有向边(x,y)变为直接连 2019-10-01 算法
POJ 2060 最小路径覆盖 POJ 2060 题意 给出n个任务,每个任务是在规定的开始时间使 计程车 从二维平面A到达B点.并且求完成所有任务所需要的计程车的最少数量? 思路 将每个任务看做有向无环图中的一个点.如果上一个任务完成后能在另一个任务开始时间之前到达这个任务的起点.那么建有向边. 为了完成所有任务(覆盖有向图所有的点)且调用的出租车最少(用最少的路径来覆盖有向图).问题转化成了最小路径覆盖 有向无环图最 2019-10-01 算法