最新二分图匹配及其应用课件

二分图匹配及其应用二分图匹配及其应用目录增广路定理与Hall定理二分图最大基数匹配二分图最大权匹配应用目录增广路定理与Hall定理2最新二分图匹配及其应用课件3最新二分图匹配及其应用课件4最新二分图匹配及其应用课件5最新二分图匹配及其应用课件6最新二分图匹配及其应用课件7最新二分图匹配及其应用课件8Hopcroft算法可以证明：如果每次找到的最短增广路集是极大的，则只需要增广次关键：用O(m)时间找一个极大最短增广路集步骤1：用距离标号扩展匈牙利树，找到第一个未盖点时并不停止，把此时的距离标号设为上限。这样，找到的所有未盖点距离标号都相同步骤2：每次任取一个未盖点，用DFS找到它到起点的增广路(只沿着距离标号下降的方向),标记经过的点,找所有增广路的总时间为O(m)Hopcroft算法可以证明：如果每次找到的最短增广路集是极9基于DFS的算法从贪心匹配,而不是空匹配开始每次从一个未盖点开始DFS找增广路,而不是一次性把所有未盖点放入队列进行BFS如果从一个未盖点u开始找不到增广路,则以后再也不用考虑u了.为什么?定理:假设G的匹配为M,不存在从非饱和点u出发的增广路,而存在另外一条增广路P,则G也不存在从u出发关于增广后新匹配的增广路基于DFS的算法从贪心匹配,而不是空匹配开始10定理的证明(1)定理:假设G的匹配为M,不存在从非饱和点u出发的增广路,而存在另外一条增广路P,则G也不存在从u出发关于增广后新匹配M’的增广路证明:假设增广后从u出发有增广路Q.若Q与P不相交,则Q就是M-增广路,矛盾.因此Q与P相交.下面借助P和Q构造出从u出发关于M的增广路,从而得到矛盾定理的证明(1)定理:假设G的匹配为M,不存在从非饱和点11定理的证明(2)Q与P相交.设P的两个M-非饱和点为u0和v0,而Q的两个M’-非饱和点是u,v.从u开始沿Q走,设第一个P中结点为w,则w把P分为两段,其中必有一段以M中边与w关联,得到从u出发增广路wv0u0vuPQ定理的证明(2)Q与P相交.设P的两个M-非饱和点为u0和12完全二分图的最大权完美匹配完全二分图，每条边有一个非负整数权值目标：求出权和最大的完美匹配特点：完美匹配容易求，但权最大的不易可行顶标：结点函数l，对任意弧(x,y)满足相等子图：G的生成子图，包含所有点，但只包含满足l(x)+l(y)=w(x,y)的所有弧(x,y)完全二分图的最大权完美匹配完全二分图，每条边有一个非负整数权13相等子图定理：如果相等子图有完美匹配，则该匹配是原图的最大权匹配证明：设M*是相等子图的完美匹配，则根据定义设M是原图的任意完美匹配，则关键：寻找好的可行顶标，使相等子图有完美匹配相等子图定理：如果相等子图有完美匹配，则该匹配是原图的最大权14算法思想关键：寻找好的可行顶标，使相等子图有完美匹配思想：随便构造一个可行顶标（例如Y结点顶标为0，X结点的顶标为它出发所有弧的最大权值，然后求相等子图的最大匹配存在完美匹配，算法终止否则修改顶标使得相等子图的边变多，有更大机会存在完美匹配考虑相等子图不存在完美匹配时的情形算法思想关键：寻找好的可行顶标，使相等子图有完美匹配15Kuhn-Munkres算法如右图，相等子图的最大匹配基数为6，不是完美匹配算法在寻找增广路失败的同时得到了一棵匈牙利树虽然此匈牙利树并没有包含未盖点（因此没有找到增广路），但仍然含有重要信息Kuhn-Munkres算法如右图，相等子图的最大匹配基数为16Kuhn-Munkres算法设匈牙利树中的X结点集为S，Y结点集为T，则S到T没有边（否则匈牙利树可以继续生长）S到T的边都是非匹配边（想一想，为什么）但若把S中所有点的顶标同时减少一个相同整数a，则S到T中可能会有新边进入相等子图SSTTKuhn-Munkres算法设匈牙利树中的X结点集为S，Y结17Kuhn-Munkres算法把S中所有点的顶标同时减少一个相同整数a，则S到T中可能会有新边进入相等子图为了保证S-T的匹配边不离开相等子图，把T中所有点的顶标同时增加aSSTT-a+a为保证有新边进入，取如果S中每个顶标的实际减小值比这个值小则不会有新边进入；如果比这个值大则顶标将变得不可行Kuhn-Munkres算法把S中所有点的顶标同时减少一个相18Kuhn-Munkres算法设边(x,y)进入相同子图y是未盖点，则找到增广路y和S中的点z匹配，则把z和y分别加入S和T中每次修改顶标要么找到增广路，要么使匈牙利树增加两个结点因此一共需要O(n2)次修改顶标操作关键：快速修改顶标SSTT-a+aKuhn-Munkres算法设边(x,y)进入相同子图SST19顶标的修改方法1：枚举S和T中的每个元素，根据定义计算最小值，每次修改的时间为O(n2)，总O(n4)方法2：对于T中的每个元素y，定义松弛量则a的计算公式变为顶标的修改方法1：枚举S和T中的每个元素，根据定义计算最小值20顶标的快速修改每次增广后用O(n2)时间计算所有点的初始slack，由于每次生长匈牙利树时所有S-T弧的增量相同，因此修改每个slack值只需要常数时间，计算所有slack值需要O(n)时间每次增广后最多修改n次顶标，因此每次增广后修改顶标总时间降为O(n2)，总O(n3)结论：Kuhn-Munkres算法的总时间复杂度为O(n3)顶标的快速修改每次增广后用O(n2)时间计算所有点的初始sl21例题1.BelovedSons(SGU210)国王有N个儿子，另外有N漂亮的女孩，每个儿子喜欢其中的某些。国王对每个儿子有一个喜爱程度。要把王子和这些女孩配对（不一定完全配对），使得所有被配对的王子被喜爱程度值的平方和尽可能大。例题1.BelovedSons(SGU210)国王有N22分析可以用二分图的最佳匹配因为这个图有特殊性，男孩子一边任一个点连出的所有边的权值都是相同的，所以只要将男孩子按照国王的喜欢程度从大到小排序，先对国王更喜欢的孩子扩展增广路径，就可以得到最优解。这是为什么呢？分析可以用二分图的最佳匹配23分析由增广路的性质可以知道一条增广路的应用只可能在匹配的男孩子中加入一个人，而不可能删去任意一个人。所以国王喜欢程度较低的男孩子进入匹配不可能对喜欢程度较高的孩子是否在匹配中产生任何影响：这就是贪心算法成立的原因。分析由增广路的性质可以知道一条增广路的应用只可能在匹配的男孩24例题2.Dominoes(SGU190)给定一个N×N的棋盘，其中有一些格子被移除。要求在剩下的棋盘中放置互不重叠的1×2的骨牌，将棋盘盖满。例题2.Dominoes(SGU190)给定一个N×N的棋25分析将棋盘黑白染色，使得黑格周围都是白格，白格周围都是黑格。黑白格构成了二分图的两个顶点集合，相邻的格子之间有边。这样，二分图的完备匹配就是问题的解了。实际上不需要单独建立二分图，直接在图上操作即可。点和边都是O(N2)个,因此时间复杂度为O(N3)分析将棋盘黑白染色，使得黑格周围都是白格，白格周围都是黑格。26例题3.Speleology(POI9906)一个山上有一个很大的洞，其中有n个室，编号为1~n，室与室之间有通道。编号越大的室在越下方。有一批洞穴学者要从编号为1的室走到编号为n的室中，途中他们只能从编号小的地方走到编号大的地方。每条和1或n相连的通道只允许一个人通过。问：最多可以有多少名洞穴学者？例题3.Speleology(POI9906)一个山上有一27分析我们可以把n个室看作n个点，把通道看作是点到点之间的一条有向边。那么本题就是一个典型的网络流问题。其中，每条和1或n相连的边容量为1,其他边容量为无穷大。1为源点，n为汇点。这个网络的最大流即为问题的解其实这个图是特殊的,考虑1出发直接可达集合S和直接可达n的集合T之间的最大匹配分析我们可以把n个室看作n个点，把通道看作是点到点之间的一28例题4.UnstableSystems(SGU218)求一个完备匹配，使得匹配边中权值最大的边权值最小。例题4.UnstableSystems(SGU218)求29分析算法一二分选择flow，并且进行最大匹配算法二从权值最低的边开始，每次增加一条边。维护交错树森林，最多只可能增加一个交错轨。因为找到N条交错轨即可，而维护交错树森林的平摊复杂度为O(1)，所以总时间复杂度依然为O(N3)分析算法一30例题5.GreedyIsland(ZOJ1638)有n(<=10,000)种卡片，每种卡片上有三种属性：攻击、防御、超能力从n张卡片中选A张作为攻击卡片，B张作为防御卡片，C张作为超能力卡片(A+B+C<=100)。要求攻击卡片的总攻击值、防御卡片的总防御值和超能力卡片的总超能力值之和尽量大例题5.GreedyIsland(ZOJ1638)有n31分析令A+B+C=m，则m<=100如果一张卡片被选为攻击卡片，则它的攻击值不可能排不到前m位（这样前m位肯定有没选的，换成它则提高攻击值）这样，只需要保留攻击、防御和超能力各前100名，一共最多3m张（有重复的话比这个少）。分析令A+B+C=m，则m<=10032分析算法一：构造二分图，左边3个点，表示攻击、防御、超能力三个用途；右边3m个点，表示所有需要考虑的卡片，则时间复杂度为O(m3)。算法二：左边只有3个点，因此可以设d[i,a,b,c]表示前i张选了a张攻击卡片，b张防御卡片，c张超能力卡片，则状态转移是O(1)的（考虑下一张卡片的四种决策），状态不超过m4/9个，仍然高效分析算法一：构造二分图，左边3个点，表示攻击、防御、超能力三33例题6.DivideandConquer(SGU229)N*N的方格上有一些格子着黑色.把它们分成两部分,使得其中一部分逆时针旋转90度、180度或270度后再平移,可以和另一部分重合例题6.DivideandConquer(SGU22934分析枚举旋转角度和平移向量,枚举量O(n2)每个点变换后有一个唯一的象.对于每个黑点p,如果它的象也是黑点,则连一条有向边则问题有解当且仅当此图有完美匹配如果得到的图有度数为0的点或者自环,显然没有匹配,否则图是链和环的集合,各个连通分量很容易求出各自的最大匹配时间复杂度为:O(n4)分析枚举旋转角度和平移向量,枚举量O(n2)35例题7.整数因子团问题给整数n,考虑集合{1,2,…,n}.每次可以选择集合中的一个元素k,删除它和它在集合中的所有因子,要求每次至少删除两个数(即k至少有一个小于k的约数在集合中)例如,n=6时方案一:依次选5,6,剩余序列为4方案二:依次选5,4,6,剩余序列为空输入n(<=120),求一种方案让选择的数之和尽量大.注意选择的数并不等同于删除的数例题7.整数因子团问题给整数n,考虑集合{1,2,…36分析似乎并没有很好的方法,搜索吧下界:一个不错的解,先贪心,搜索过程中不断改进为当前得到的最优解上界:对当前状态的估计,应被设计为状态的函数.因为频繁调用,计算量不应太大关键:最优性剪枝当前分数+当前状态的上界<=下界分析似乎并没有很好的方法,搜索吧37贪心先考虑只有两个约数的数中最大的一个,如果没有,再考虑只有三个约数的数中最大的一个.只有一种情况例外:如果q有一个倍数p,使得边p->q存在且p出发只有一条边.删除q会让p没有办法删除,还不如主动选择p,效果是一样的.如果有多个p,显然应选择最大的一个时间复杂度:O(nlog2n)贪心先考虑只有两个约数的数中最大的一个,如果没有,再考虑38上界集合中每个数一个点,a/b是素数,则连一条边a->b,则数a是数b的倍数当且仅当a到b有有向道路.这样构图的好处是边比较少结论:如果a可选,则a出发一定有边.证明:如果a出发的边都不存在了，则根据游戏规则它的所有后代都将被删除,与a可选矛盾.最好情况:每次只被动删除一个数上界集合中每个数一个点,a/b是素数,则连一条边a->b39匹配每条边a->b的权是a,则“每次选一个数删一个数”的最大得分是图的最大权匹配结论：不考虑边的方向，这个图是二分图证明：考虑每个数u的惟一分解式每条边(u,v)满足u/v=p是素数，因此v的分解式中指数之和减1，奇偶性改变分解式中指数和为奇/偶的结点为X/Y结点匹配每条边a->b的权是a,则“每次选一个数删一个数”的最40匹配只是上界考虑以下匹配：a)2—22，b)3—39，c)11—33，d)13—26不难得出：a)在d)之前，d)在b)之前，b)在c)之前，c)在a)之前。而这是不可能实现的不过n比较小时匹配结果就是标准答案虽然如此,这个上界是相容的,可以用作IDA*算法的估价函数匹配只是上界考虑以下匹配：41不明智的选择a至少有4个约数(包括自己),其中至少有一个比a的层次小2i)先删b更好ii)先删c更好iii)不会出现(设b/c=p1,b/d=p2,则a/p1和a/p2分别是c和d的倍数,故没删除.但它们应和b同层)bacdbaabcd不明智的选择a至少有4个约数(包括自己),其中至少有一个比42其他优化检查相邻操作是否可交换猜想:存在一个数只有两个约数没有被删除,并且这个数的所有倍数(除了它自己)已被删除,那么删除满足条件的最大数是最优的a2cabacab2abcb2cbcca2bac2bc2其他优化检查相邻操作是否可交换a2cabacab2abcb243猜想的反例a,b,c是不同素数,a<b<c,a2b<[n/2]贪心:方案先删除,ab2,后面最大ac2+bc2更优方案:先删除ac2,再bc2,再abc但n<=120时反例不会出现a2cabacab2abcb2cbcca2bac2bc2猜想的反例a,b,c是不同素数,a<b<c,a2b<[n/44运行结果如果不用猜想,则70~74,81~86,105~120都很慢用上猜想则所有数据0.5秒以内出解N1030506580100105110120答案40301808132820413164343437644593运行结果如果不用猜想,则70~74,81~86,10545

结束语谢谢大家聆听！！！46

结束语谢谢大家聆听！！！46二分图匹配及其应用二分图匹配及其应用目录增广路定理与Hall定理二分图最大基数匹配二分图最大权匹配应用目录增广路定理与Hall定理48最新二分图匹配及其应用课件49最新二分图匹配及其应用课件50最新二分图匹配及其应用课件51最新二分图匹配及其应用课件52最新二分图匹配及其应用课件53最新二分图匹配及其应用课件54Hopcroft算法可以证明：如果每次找到的最短增广路集是极大的，则只需要增广次关键：用O(m)时间找一个极大最短增广路集步骤1：用距离标号扩展匈牙利树，找到第一个未盖点时并不停止，把此时的距离标号设为上限。这样，找到的所有未盖点距离标号都相同步骤2：每次任取一个未盖点，用DFS找到它到起点的增广路(只沿着距离标号下降的方向),标记经过的点,找所有增广路的总时间为O(m)Hopcroft算法可以证明：如果每次找到的最短增广路集是极55基于DFS的算法从贪心匹配,而不是空匹配开始每次从一个未盖点开始DFS找增广路,而不是一次性把所有未盖点放入队列进行BFS如果从一个未盖点u开始找不到增广路,则以后再也不用考虑u了.为什么?定理:假设G的匹配为M,不存在从非饱和点u出发的增广路,而存在另外一条增广路P,则G也不存在从u出发关于增广后新匹配的增广路基于DFS的算法从贪心匹配,而不是空匹配开始56定理的证明(1)定理:假设G的匹配为M,不存在从非饱和点u出发的增广路,而存在另外一条增广路P,则G也不存在从u出发关于增广后新匹配M’的增广路证明:假设增广后从u出发有增广路Q.若Q与P不相交,则Q就是M-增广路,矛盾.因此Q与P相交.下面借助P和Q构造出从u出发关于M的增广路,从而得到矛盾定理的证明(1)定理:假设G的匹配为M,不存在从非饱和点57定理的证明(2)Q与P相交.设P的两个M-非饱和点为u0和v0,而Q的两个M’-非饱和点是u,v.从u开始沿Q走,设第一个P中结点为w,则w把P分为两段,其中必有一段以M中边与w关联,得到从u出发增广路wv0u0vuPQ定理的证明(2)Q与P相交.设P的两个M-非饱和点为u0和58完全二分图的最大权完美匹配完全二分图，每条边有一个非负整数权值目标：求出权和最大的完美匹配特点：完美匹配容易求，但权最大的不易可行顶标：结点函数l，对任意弧(x,y)满足相等子图：G的生成子图，包含所有点，但只包含满足l(x)+l(y)=w(x,y)的所有弧(x,y)完全二分图的最大权完美匹配完全二分图，每条边有一个非负整数权59相等子图定理：如果相等子图有完美匹配，则该匹配是原图的最大权匹配证明：设M*是相等子图的完美匹配，则根据定义设M是原图的任意完美匹配，则关键：寻找好的可行顶标，使相等子图有完美匹配相等子图定理：如果相等子图有完美匹配，则该匹配是原图的最大权60算法思想关键：寻找好的可行顶标，使相等子图有完美匹配思想：随便构造一个可行顶标（例如Y结点顶标为0，X结点的顶标为它出发所有弧的最大权值，然后求相等子图的最大匹配存在完美匹配，算法终止否则修改顶标使得相等子图的边变多，有更大机会存在完美匹配考虑相等子图不存在完美匹配时的情形算法思想关键：寻找好的可行顶标，使相等子图有完美匹配61Kuhn-Munkres算法如右图，相等子图的最大匹配基数为6，不是完美匹配算法在寻找增广路失败的同时得到了一棵匈牙利树虽然此匈牙利树并没有包含未盖点（因此没有找到增广路），但仍然含有重要信息Kuhn-Munkres算法如右图，相等子图的最大匹配基数为62Kuhn-Munkres算法设匈牙利树中的X结点集为S，Y结点集为T，则S到T没有边（否则匈牙利树可以继续生长）S到T的边都是非匹配边（想一想，为什么）但若把S中所有点的顶标同时减少一个相同整数a，则S到T中可能会有新边进入相等子图SSTTKuhn-Munkres算法设匈牙利树中的X结点集为S，Y结63Kuhn-Munkres算法把S中所有点的顶标同时减少一个相同整数a，则S到T中可能会有新边进入相等子图为了保证S-T的匹配边不离开相等子图，把T中所有点的顶标同时增加aSSTT-a+a为保证有新边进入，取如果S中每个顶标的实际减小值比这个值小则不会有新边进入；如果比这个值大则顶标将变得不可行Kuhn-Munkres算法把S中所有点的顶标同时减少一个相64Kuhn-Munkres算法设边(x,y)进入相同子图y是未盖点，则找到增广路y和S中的点z匹配，则把z和y分别加入S和T中每次修改顶标要么找到增广路，要么使匈牙利树增加两个结点因此一共需要O(n2)次修改顶标操作关键：快速修改顶标SSTT-a+aKuhn-Munkres算法设边(x,y)进入相同子图SST65顶标的修改方法1：枚举S和T中的每个元素，根据定义计算最小值，每次修改的时间为O(n2)，总O(n4)方法2：对于T中的每个元素y，定义松弛量则a的计算公式变为顶标的修改方法1：枚举S和T中的每个元素，根据定义计算最小值66顶标的快速修改每次增广后用O(n2)时间计算所有点的初始slack，由于每次生长匈牙利树时所有S-T弧的增量相同，因此修改每个slack值只需要常数时间，计算所有slack值需要O(n)时间每次增广后最多修改n次顶标，因此每次增广后修改顶标总时间降为O(n2)，总O(n3)结论：Kuhn-Munkres算法的总时间复杂度为O(n3)顶标的快速修改每次增广后用O(n2)时间计算所有点的初始sl67例题1.BelovedSons(SGU210)国王有N个儿子，另外有N漂亮的女孩，每个儿子喜欢其中的某些。国王对每个儿子有一个喜爱程度。要把王子和这些女孩配对（不一定完全配对），使得所有被配对的王子被喜爱程度值的平方和尽可能大。例题1.BelovedSons(SGU210)国王有N68分析可以用二分图的最佳匹配因为这个图有特殊性，男孩子一边任一个点连出的所有边的权值都是相同的，所以只要将男孩子按照国王的喜欢程度从大到小排序，先对国王更喜欢的孩子扩展增广路径，就可以得到最优解。这是为什么呢？分析可以用二分图的最佳匹配69分析由增广路的性质可以知道一条增广路的应用只可能在匹配的男孩子中加入一个人，而不可能删去任意一个人。所以国王喜欢程度较低的男孩子进入匹配不可能对喜欢程度较高的孩子是否在匹配中产生任何影响：这就是贪心算法成立的原因。分析由增广路的性质可以知道一条增广路的应用只可能在匹配的男孩70例题2.Dominoes(SGU190)给定一个N×N的棋盘，其中有一些格子被移除。要求在剩下的棋盘中放置互不重叠的1×2的骨牌，将棋盘盖满。例题2.Dominoes(SGU190)给定一个N×N的棋71分析将棋盘黑白染色，使得黑格周围都是白格，白格周围都是黑格。黑白格构成了二分图的两个顶点集合，相邻的格子之间有边。这样，二分图的完备匹配就是问题的解了。实际上不需要单独建立二分图，直接在图上操作即可。点和边都是O(N2)个,因此时间复杂度为O(N3)分析将棋盘黑白染色，使得黑格周围都是白格，白格周围都是黑格。72例题3.Speleology(POI9906)一个山上有一个很大的洞，其中有n个室，编号为1~n，室与室之间有通道。编号越大的室在越下方。有一批洞穴学者要从编号为1的室走到编号为n的室中，途中他们只能从编号小的地方走到编号大的地方。每条和1或n相连的通道只允许一个人通过。问：最多可以有多少名洞穴学者？例题3.Speleology(POI9906)一个山上有一73分析我们可以把n个室看作n个点，把通道看作是点到点之间的一条有向边。那么本题就是一个典型的网络流问题。其中，每条和1或n相连的边容量为1,其他边容量为无穷大。1为源点，n为汇点。这个网络的最大流即为问题的解其实这个图是特殊的,考虑1出发直接可达集合S和直接可达n的集合T之间的最大匹配分析我们可以把n个室看作n个点，把通道看作是点到点之间的一74例题4.UnstableSystems(SGU218)求一个完备匹配，使得匹配边中权值最大的边权值最小。例题4.UnstableSystems(SGU218)求75分析算法一二分选择flow，并且进行最大匹配算法二从权值最低的边开始，每次增加一条边。维护交错树森林，最多只可能增加一个交错轨。因为找到N条交错轨即可，而维护交错树森林的平摊复杂度为O(1)，所以总时间复杂度依然为O(N3)分析算法一76例题5.GreedyIsland(ZOJ1638)有n(<=10,000)种卡片，每种卡片上有三种属性：攻击、防御、超能力从n张卡片中选A张作为攻击卡片，B张作为防御卡片，C张作为超能力卡片(A+B+C<=100)。要求攻击卡片的总攻击值、防御卡片的总防御值和超能力卡片的总超能力值之和尽量大例题5.GreedyIsland(ZOJ1638)有n77分析令A+B+C=m，则m<=100如果一张卡片被选为攻击卡片，则它的攻击值不可能排不到前m位（这样前m位肯定有没选的，换成它则提高攻击值）这样，只需要保留攻击、防御和超能力各前100名，一共最多3m张（有重复的话比这个少）。分析令A+B+C=m，则m<=10078分析算法一：构造二分图，左边3个点，表示攻击、防御、超能力三个用途；右边3m个点，表示所有需要考虑的卡片，则时间复杂度为O(m3)。算法二：左边只有3个点，因此可以设d[i,a,b,c]表示前i张选了a张攻击卡片，b张防御卡片，c张超能力卡片，则状态转移是O(1)的（考虑下一张卡片的四种决策），状态不超过m4/9个，仍然高效分析算法一：构造二分图，左边3个点，表示攻击、防御、超能力三79例题6.DivideandConquer(SGU229)N*N的方格上有一些格子着黑色.把它们分成两部分,使得其中一部分逆时针旋转90度、180度或270度后再平移,可以和另一部分重合例题6.DivideandConquer(SGU22980分析枚举旋转角度和平移向量,枚举量O(n2)每个点变换后有一个唯一的象.对于每个黑点p,如果它的象也是黑点,则连一条有向边则问题有解当且仅当此图有完美匹配如果得到的图有度数为0的点或者自环,显然没有匹配,否则图是链和环的集合,各个连通分量很容易求出各自的最大匹配时间复杂度为:O(n4)分析枚举旋转角度和平移向量,枚举量O(n2)81例题7.整数因子团问题给整数n,考虑集合{1,2,…,n}.每次可以选择集合中的一个元素k,删除它和它在集合中的所有因子,要求每次至少删除两个数(即k至少有一个小于k的约数在集合中)例如,n=6时方案一:依次选5,6,剩余序列为4方案二:依次选5,4,6,剩余序列为空输入n(<=120),求一种方案让选择的数之和尽量大.注意选择的数并不等同于删除的数例题7.整数因子团问题给整数n,考虑集合{1,2,…82分析似乎并没有很好的方法,搜索吧下界:一个不错的解,先贪心,搜索过程中不断改进为当前得到的最优解上界:对当前状态的估计,应被设计为状态的函数.因为频繁调用,计算量不应太大关键:最优性剪枝当前分数+当前状态的上界<=下界分析似乎并没有很好的方法,搜索吧83贪心先考虑只有两个约数的数中最大的一个,如果没有,再考虑只有三个约数的数中最大的一个.只有一种情况例外:如果q有一个倍数p,使得边p->q存在且p出发只有一条边.删除q会让p没有办法删除,还不如主动选择p,效果是一样的.如果有多个p,显然应选择最大的一个时间复杂度:O(nlog2n)贪心先考虑只有