KM算法

km算法我的理解 刷了不到20道题。。。回来总结一发。。

hdu 3523 题目链接 题意：有m个排列，每个排列有n个，然后要找一个长度为n的排列（1..n每个数字恰好出现一次），使得这个排列到其他m个排列的距离之和最小。 两个排列之间的距离是对应位置上数字差的绝对值的和。

hdu 3315 题目链接 题意：两个人分别各有 n 个怪物。进行 n 场 pk。每只怪物必须恰好进行一场 pk。如果先手的第 i 只怪物赢，会获得 v[i] 的 val，输会减少 v[i] 的 val。给出两个人 n 只怪物的血量和攻击力。先手的初始战斗顺序为 1,2,3..n（后手的战斗顺序一直都是 1,2,3..n）现在问能否通过调整顺序使得先手获得的 val 最大，如果这个 val 大于 0，表示先手可以赢。如果可以赢，那么还要求调整后的顺序和原始顺序的相似度，并且使得相似度尽可能大（If there are multiple orders, you should choose the one whose order changes the least from the original one）

hdu 2853 题目链接 题意：n 个公司，m 个任务（m>=n)，一个公司只能对应一个任务，一个任务也只能对应一个公司。给出一个 n*m 的 mat，表示每个公司对应每个任务产生的 val。然后给出 n 个数，表示初始钦定（雾）这 n 个公司分别做哪些任务。但是可能初始的安排得到的 val 不是最大的。我们现在想得到最大的 val，并且保证改变的安排数最少。求安排后得到的 val 比初始安排大多少，以及需要改变的安排数量。

hdu2448 题目链接 题意：n 艘船 n 个港口，一个港口只能承接一艘船，m 个油田，给出 n 艘船各自在哪个油田，然后给出 m 个油田之间的无向图，然后给出油田和港口之间的有向图。求 n 艘船到达港口的最小距离之和。

hdu 3718题目链接 题意：东西分类作业，有n个东西，k组，m个学生，不同种类的东西用不同的字母表示，相同种类的用同一个字母表示。不同学生和标准答案之间可能表示同一类东西用的字母不同，但是字母只是一个标号（But the LABEL of group doesn’t make sense and the LABEL is just used to indicate different groups. ） 给出事物分类的标准答案和每个学生的答案现在问每个学生的正确率是多少。

hdu 3722题目链接 题意：n个串，a串放在b串前面的val值是“The score of sticking two cards is the longest common prefix of the second card and the reverse of the first card”.问如何放使得总的val最大。

hdu 3435题目链接 题意：给你一张图，图上可能有多个哈密顿回路。叫你求出形成多个哈密顿回路的总距离最小值

hdu 1853 题目链接 题意：一个带权有向图，要求找出若干的环，满足每个点恰好在一个环里，并且环的权值和最小……问最小权值和。

hdu 2813 题目链接 题意：吕布有n个武将，曹操有m（m>=n）个武将。给出k个关系，为吕布的某个武将和曹操的某个武将pk后会受到的伤害。吕布要求他所有n的武将都要上场，每个武将只能战斗一次，问如何安排，使得所有武将受到的伤害总和最小。

hdu 2282 题目链接 题意：n个盒子围成一个圈，给出n个盒子中每个盒子中的巧克力个数，巧克力的总数不超过n，从一个盒子中移动一块巧克力到相邻的盒子里称为one “move”，（由于围成一个圈，所以第1个和第n个盒子也是相邻的） 问最小的移动“move”数，使得每个盒子里最多有一快巧克力。

hdu 3395题目链接 题意：鱼，一些鱼认为自己是汉子，然后他会去和他认为是妹子的鱼啪啪啪，然后被啪啪啪的妹子就会产卵？ 卵的val是它parent的val的异或。给出n，为鱼的数量，然后给出一个n*n的 mat,a[i][j]==1表示第i条鱼认为第j条鱼是妹子。问卵的最大val之和是多少。需要注意的是：每条鱼最多可以去和一个妹子啪，并且可以作为妹子被啪一次（这两个是独立的。。。） （Each fish can attack one other fish and can only be attacked once）

hdu 2426 题目链接 题意：n个学生，m个宿舍，每个学生住一个宿舍，然后n个学生给若干个宿舍打分，分数可正可0可负，学生不能住打的分为负的宿舍，或者没有打分的宿舍。问在满足上述条件的前提下，所有学生住的宿舍的分数之和最大是多少。如果无解输出-1.

hdu 1533 题目链接 题意：给出一个 n*m 的 maze，其中包含一些人（用 m 表示），以及和人数相等的房子（用 H 表示），其他都是‘.’，表示可以经过的路径。人向一个方向移动花费代价 1。问每个人都回到一个房子里的最小代价是多少。ps：每个格子是无限大的，也就是所有人可以同时踩在一个格子里。以及：路过一个房子可以不住，而只是“经过”。

hdu 2255 题目链接 题意：传说在遥远的地方有一个非常富裕的村落，有一天，村长决定进行制度改革：重新分配房子。 这可是一件大事，关系到人民的住房问题啊。村里共有 n 间房间，刚好有 n 家老百姓，考虑到每家都要有房住（如果有老百姓没房子住的话，容易引起不安定因素），每家必须分配到一间房子且只能得到一间房子。 另一方面，村长和另外的村领导希望得到最大的效益，这样村里的机构才会有钱。由于老百姓都比较富裕，他们都能对每一间房子在他们的经济范围内出一定的价格，比如有 3 间房子，一家老百姓可以对第一间出 10 万，对第 2 间出 2 万，对第 3 间出 20 万。（当然是在他们的经济范围内）现在这个问题就是村领导怎样分配房子才能使收入最大。（村民即使有钱购买一间房子但不一定能买到，要看村领导分配的）。