匈牙利算法时间复杂度

㈠ NOI考试的内容是什么

1 时间复杂度（渐近时间复杂度的严格定义，NP问题，时间复杂度的分析方法，主定理）
2 排序算法（平方排序算法的应用，Shell排序，快速排序，归并排序，时间复杂度下界，三种线性时间排序，外部排序）
3 数论（整除，集合论，关系，素数，进位制，辗转相除，扩展的辗转相除，同余运算，解线性同余方程，中国剩余定理）
4 指针（链表，搜索判重，邻接表，开散列，二叉树的表示，多叉树的表示）
5 按位运算（and，or，xor，shl，shr，一些应用）
6 图论（图论模型的建立，平面图，欧拉公式与五色定理，求强连通分量，求割点和桥，欧拉回路，AOV问题，AOE问题，最小生成树的三种算法，最短路的三种算 法，标号法，差分约束系统，验证二分图，Konig定理，匈牙利算法，KM算法，稳定婚姻系统，最大流算法，最小割最大流定理，最小费用最大流算法）
7 计算几何（平面解几及其应用，向量，点积及其应用，叉积及其应用，半平面相交，求点集的凸包，最近点对问题，凸多边形的交，离散化与扫描）
8 数据结构（广度优先搜索，验证括号匹配，表达式计算，递归的编译，Hash表，分段Hash，并查集，Tarjan算法，二叉堆，左偏树，斜堆，二项堆，二叉查找树，AVL，Treap，Splay，静态二叉查找树，2-d树，线段树，二维线段树，矩形树，Trie树，块状链表）
9 组合数学（排列与组合，鸽笼原理，容斥原理，递推，Fibonacci数列，Catalan数列，Stirling数，差分序列，生成函数，置换，Polya原理）
10 概率论（简单概率，条件概率，Bayes定理，期望值）
11 矩阵（矩阵的概念和运算，二分求解线性递推方程，多米诺骨牌棋盘覆盖方案数，高斯消元）
12 字符串处理（KMP，后缀树，有限状态自动机，Huffman编码，简单密码学）
13 动态规划（单调队列，凸完全单调性，树型动规，多叉转二叉，状态压缩类动规，四边形不等式）
14 博奕论（Nim取子游戏，博弈树，Shannon开关游戏）
15 搜索（A*，ID，IDA*，随机调整，遗传算法）
16 微积分初步（极限思想，导数，积分，定积分，立体解析几何）

㈡ 拍卖算法和匈牙利算法优缺点

1、拍卖算法优点拍卖可以促进标的物拍值最大化，最大程度的保护当事人的利益，并为公众创造了良好的竞拍环境，扩大了竞拍参与机会。网络拍卖对竞拍者而言，突破了地域限制，享受着足不出户，动动鼠标就可以充分的了解拍品的信息和价格并参与竞拍，使得参拍人数没有限制，大大增加了参拍机率的同时，促使拍卖物交易价格的最大化，最大程度保护当事人的利益。缺点是对于竞拍者的保护问题值得探讨。
2、匈牙利算法是一种组合优化算法，是解决多项式时间复杂度问题的较快方法。匈牙利法最大的缺点是烦琐匈牙利算法的思想非常暴力，就是对于个边，能连就直接连，不能连就尝试让之前的点给当前点腾出来一个点。

㈢ DFS的效率

作为搜索算法的一种，DFS对于寻找一个解的NP（包括NPC）问题作用很大。但是，搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法，它的效率比较低，在数据规模变大时，这种算法就显得力不从心了。
关于深度优先搜索的效率问题，有多种解决方法。最具有通用性的是剪枝（prunning），也就是去除没有用的搜索分支。有可行性剪枝和最优性剪枝两种。此外，对于很多问题，可以把搜索与动态规划（DP,dynamic programming)、完备匹配（匈牙利算法）等高效算法结合。

㈣ 数学建模中哪些东西是放在附件中的

1最短路问题（SPP－shortestpathproblem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。2公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？3指派问题（assignmentproblem）一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？4中国邮递员问题（CPP－chinesepostmanproblem）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。5旅行商问题（TSP－travelingsalesmanproblem）一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。6运输问题（transportationproblem）某种原材料有个产地，现在需要将原材料从产地运往个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？7.最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法8.计算赋权图中各对顶点之间最短路径，显然可以调用Dijkstra算法。具体方法是：每次以不同的顶点作为起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，反复执行n次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为O(n^3)。第二种解决这一问题的方法是由FloydRW提出的算法，称之为Floyd算法。(可以解决第一个问题)9.prim算法、Kruskal算法构造最小生成树（使所有点连通）10.匈牙利算法、Kuhn-Munkres算法解决人员分配问题11.Euler回路的Fleury算法（中国邮递员问题）12.最大流的一种算法—标号法（用标号法寻求网络中最大流的基本思想是寻找可增广轨，使网络的流量得到增加，直到最大为止。）我的计算机不好，用的是MATLAB，网上很多资料可以网络到。程序好直接网络对应算法搞成C的吧……算法很多网络能到……

㈤ km算法中两方数目不等应当怎么改该算法 附：c++程序

将点比较少的那一部扩充，使得其点数与另一部相同，再将两部之间不相邻的点连上边权为0的边，则问题转化成点数相同的问题。