有个北大的教授来学校讲了《社会问题的中的计算机思维浅赏》。
讲到有关二部图问题的地方发现很像KM算法，就把KM拿出来复(yu)习(xi)了一遍。 
简介：
用来解决带权二部图匹配。
优势：
相比费用流，常数小，代码复杂度低。
适用于某些特定的题目。
简介：
定义一个二部图G，左顶点为X，右顶点为Y，边权为Wij。
设左顶点上有点标A,右顶点B，满足对于任意的点对(i,j)，Ai+Bj>=Wij。
引理：定义二部图G的一个以 （X , Y , 所有满足Ai+Bj==Wij的边） 组成的集合为S。
那么，对于一个S的完备匹配，一定是G的最大完备匹配。
此时，这个完备匹配对应的答案即为所有的顶标和。
伪证明：如果G的某一个完备匹配的某条边(i,j)不在集合S中，那么Wij<=Ai+Bj,所以不然不会比S中的完备匹配优。
算法流程：
1.初始化顶标。对于X，每个点的顶标为这个点连出去的边的边权的最大值。对于Y，顶标为0。
2.寻找交错路。直到无法找到。
3.设dij=Ai+Bi-Wij，对于X中在交错路中的点，找到Y中不在交错路中的点，为(i,j)，找到所有满足条件的点对中dij最小的点对。
把交错路中的所有X顶标-dij，交错路中的Y顶标+dij。
{ 此时，对于一条边(i,j)。
若i在交错路中，j也在交错路中，那么Ai-dij+Bi+dij==Ai+Bi==Wij。 (无影响)
若i不在交错路中，j也不在交错路中，那么Ai+Bi>Wij。 (无影响)
若i在交错路中，j不在交错路中Ai+Bj>Ai-dij+Bj>=Wij。 (有可能进入S集合)
若i不在交错路，j在交错路中Ai+Bj+dij>Ai+Bj>Wij。 (不可能进入S集合)
}
通过上述操作，我们把至少一条边加入了S集合。
4.重复(2)(3)直到找到完备匹配。
注意：在步骤3中，我们可以在匈牙利找交错路的时候顺带在Y中记下和这个点相连的在交错路中的X的最近距离,slack数组来快速找到dij。
复杂度：这里我很纳闷，我觉得每次改点标必然加入一条边，最多改O(m)次点标，每次改点标要做一次匈牙利增广O(n+m)，我认为复杂度是O(m*(n+m))的，但是网上都 说是O(n^3)，希望有人能帮我指正！！！ 确实是O(n*m)，不过现在太迟了，不想写了。。。明天还要跑1km 
应用：
二分图带权匹配就不说了，费用流直接上就可以了。
SHOI2004MST，题意是给定一张图G和G的一棵生成树T，让你修改最小的边权使T是G的最小生成树。
对于T上的边，他一定是增加的，不在T上的边一定是减小的。
设边权为p，修改大小为d。
对于一条不在T上的边i，设他在T上跨越的边j，需要满足 pi+di>=pj-dj -> di+dj>=-pi+pj。
观察式子发现它很像KM的Ai+Bj>=Wij，然后转化为KM的点标和，直接上KM。
至于为什么KM跑出来的点标是最小的，我只能给出伪证明：
对于一个S的完备匹配，修改任何一个点的点权，使其减小d，其在另一部中对应的点权必然增加d，否则Ai+Bj>=Wij就不成立了。因此解无法变得更小。所以是最优解。
类似条件为Ai+Bj>=Wij且要求Ai，Bj的和最小的题目都可以用KM来解。
后记：
教授会动态修改Wij的KM算法哦。
虽然复杂度是O(m^2*n*)，而且算不上KM。
若有口糊请当作没听到。。求不D。。求不黑。。若有错误，欢迎指(jiao)正(yu)。。
2019年10月13日 19:20
We rely on long expression relationship with your customers thus provide companies at deals which can be well appropriate and tailored for the demands individuals customers. In order to go regarding deep washing in Dubai next book our own services today.
2021年9月15日 19:42
Consequently, floor cleaning is actually a must, and being the best traffic meeting area, you mustn't neglect the following. Your close family are wandering with grimy feet. Should there be any kid in your home, then he/she might sit and incapacitated, pick right up something and indicated in his/her teeth. So, you may understand the need. Hence, to avoid almost all these unhygienic aspects usually there are some simple tips that you should follow, that make your life a little bit easier.
2021年9月27日 22:04
You need to decide about the niche you want to set up yourself in after which concentrate upon building your company to focus on the needs of the niche marketplace. However, do not need be enclosed to only one market, since it is completely feasible in order to serve various markets through pursuing an appropriate business technique. Doing this can greatly enhance your present profit.
2021年9月27日 23:24
You will need to understand of which even understand what require almost any special expertise and skill to be happy, a beneficial education, managerial functionality and information technology knowledge is usually of good value towards business. If you could have web pattern skills it helps save a lot of money to build and maintain an internet site . of ones own to promote your online business. whatever niche you end up picking, it is usually imperative to help correctly selling price your services to make certain your small business is successful. It is usually better to help charge some sort of consolidated price for the job, based on the size, location, cost connected with living along with conditions on the place you're planning to perform in.
2022年8月19日 05:58
MyMathlab for School is a series of online Grades 9-12. Sign In. Already registered? Sign in with your Pearson account. mymathlab pearson Select this version if your MyLab Math home page looks like this: We're working with lecturers and institutions to improve results for students everywhere. -MyLab Math New Design.MyMathlab for School is a series of online Grades 9-12. Sign In. Already registered? Sign in with your Pearson account.
2022年9月06日 05:30
Here is the SMS format announced by the Mass education board, every student who has interested to check their result by SMS service can register their mobile phone number as per the following SMS format, EBT Result and this is a chargeable service by Teletak with leading telecom operates of the country. Students or their parents who have successfully registered will get the EBT Result 2022 by SMS instantly after the official announcement of the Mass Education Board, the telecom operators are fixed the SMS charges 2.44TK for every single result.
2022年9月08日 01:13
In intermediate education, Botany is a very important subject for science group students for part-1 and part-2 first and the second year of junior and senior intermediate students, and the BIEAP has conducted the General Science examination tests including botany subject, download AP inter Botany Model Paper 2023 AP 2nd Inter Botany Model Paper Pdf with solutions for all 1st and 2nd-year students for paper-1 and paper-2 exams 2023.
2023年8月28日 21:54
A vital project in particular painting the outer of ones abode might may be easy before you start but if you think the things and instruments needed in view of such style of project in addition to experience, you could possibly consider hiring a wonderful professional residing painter you can obtain. Our anticipation is usually to present people simple methods to search for the perfect household painting these individuals contractor with your neighborhood on your project.