km算法我的理解 刷了不到20道题。。。回来总结一发。。 如果题目求的是最小权值匹配，比较好的做法是将权值取取值，最后res再取负就好。需要注意的是初始化的时候w和lx要比所有值都小，所以要ms(lx,0xc0) 最正确解最小权匹配的办法是用一个很大的数-当前边权值，而不是直接对边权取反(这样只能处理左右点相等的完全二分图，即K(n, n)(bin神博客看到的) 有时候需要考虑无解的情况，一般如果有无解的情况，对应了存在lx[i]=初始化的值。 不少题目有一个点都是先用一种暴力或者不暴力的方法处理出w,然后裸的km hdu3722解题报告 有向图的覆盖可以对应二分图最佳匹配的模型，用km算法搞 hdu1853解题报告 遇到了一种题是 …

hdu 3523 题目链接 题意：有m个排列，每个排列有n个，然后要找一个长度为n的排列（1..n每个数字恰好出现一次），使得这个排列到其他m个排列的距离之和最小。 两个排列之间的距离是对应位置上数字差的绝对值的和。 思路：妈蛋，什么鬼题面。。。看不懂。。。然后看了题解。。。知道了题意。。 的的确确做过相当类似的一道呢。 先nnn的复杂度(1E6)处理权值，然后KM. 1A. /* *********************************************** Author :111qqz Created Time :2016年06月03日 星期五 19时34分36秒 File Name …

hdu 2853题目链接 题意：n个公司，m个任务（m>=n),一个公司只能对应一个任务，一个任务也只能对应一个公司。给出一个n*m的mat,表示每个公司对应每个任务产生的val。 然后给出n个数，表示初始钦定（雾）这n个公司分别做哪些任务。 但是可能初始的安排得到的val表示最大的。我们现在想得到最大的val,并且保证改变的安排数最少。求安排后得到的 val比初始安排大多少，以及需要改变的安排数量。 思路：最大val很好求，KM就好。。。但是，怎么才能保证改变的安排数最少呢？ 尤其是当两个安排val一样的时候，如何才能保证优先选已经安排好的，而不取选另一个呢？ 并没有想出来，看了题解T T 太神辣。 由于KM算法会根据权值来 …

hdu2448 题目链接 题意：n个船n个港口，一个港口只能承接一个船，m个油田，给出n个船各自在哪个油田，然后给出m个油田之间的无相图，然后给出油田和港口之间的有向图。求n个船到达港口的最小距离之和。 思路：想到了用floyd先更新一下距离，然后KM.不过思维不够严谨，只更新了港口通过油田到达油田的距离，而没有更新油田通过油田到达油田的距离QAQ. 所以应该先更新油田通过油田到达油田的距离，然后再更新港口通过油田到达油田的距离。。。 哦，还有。。。不要把n个船所对应的港口作为下标。。而是转化成1..n，这样写KM里会比较好写。。。不然总得带着那个id[i]. /* …

hdu 3718题目链接 题意：东西分类作业，有n个东西,k组，m个学生，不同种类的东西用不同的字母表示，相同种类的用同一个字母表示。不同学生和标准答案之间可能表示同一类东西用的字母不同，但是字母只是一个标号（But the LABEL of group doesn't make sense and the LABEL is just used to indicate different groups. ） 给出事物分类的标准答案和每个学生的答案现在问每个学生的正确率是多少。 思路：用map<char,int>把字母转化成点的标号。然后初始化权值为0. 对于每个学生，o(n)扫一遍统计出w。然后做一遍KM求最大正确数。从 …

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最大。 思路：先暴力处理出每两个的权值。。2002001000的复杂度。。还是可以接受的。。 然后把每个串看成了一个点，由于一个串最多可以被放在前面一次，被放在后面一次，所以可以类比图论中的环的入度和出度为1. 然后跑一遍KM. 1A,开心。 /* …

hdu 3435题目链接 题意：给你一张图，图上可能有多个哈密顿回路。叫你求出形成多个哈密顿回路的总距离最小值 思路：题意杀啊。。。什么鬼了。。。然后时间。。1000的数据。。n3复杂度。。。还多组数据。。。。不是很懂这个时间是怎么算的。。为毛才2600MS啊。。。。 做法同hdu 1853... /* *********************************************** Author :111qqz Created Time :2016年06月02日 星期四 20时13分25秒 File Name :code/hdu/1853.cpp …

hdu 1853 题目链接 题意：一个带权有向图，要求找出若干的环，满足每个点恰好在一个环里，并且环的权值和最小……问最小权值和。 思路：没有思路，不知道怎么处理环的问题。于是去群里问了下。正确做法是拆点。 如果有一条边i->j,那么就连一条i->j'的边。 正确性： 对于满足条件的环，每个点的入度和出度均为1，我们可以把每个点拆成入点和出点，那么也就是说一个入点对应一个出点，反之亦然，那么这个问题就变成了一个二分图匹配问题， 然后这道题有重边，2A. 又一次体会到了拆点的神奇。。。这个大概算是需要慢慢积累的技巧吧。。像辅助线一样的。。。 还有体会到了环的模型竟然也可以转化成二分图匹配，真是厉害== /* …

hdu 2813 题目链接 题意：吕布有n个武将，曹操有m（m>=n）个武将。给出k个关系，为吕布的某个武将和曹操的某个武将pk后会受到的伤害。吕布要求他所有n的武将都要上场，每个武将只能战斗一次，问如何安排，使得所有武将受到的伤害总和最小。 思路：裸的KM。 用map把武将名字变成点的编号。 /* *********************************************** Author :111qqz Created Time :2016年06月02日 星期四 19时17分19秒 File Name :code/hdu/2813.cpp …

hdu 2282 题目链接 题意：n个盒子围成一个圈，给出n个盒子中每个盒子中的巧克力个数，巧克力的总数不超过n，从一个盒子中移动一块巧克力到相邻的盒子里称为one “move”，（由于围成一个圈，所以第1个和第n个盒子也是相邻的） 问最小的移动“move”数，使得每个盒子里最多有一快巧克力。 思路：先记录每块巧克力的位置，为了之后算w,然后将巧克力和盒子分别看做X,Y集合。。。建图。 然后KM 。。1A /* *********************************************** Author :111qqz Created Time :2016年06月01日 星期三 21时12分48秒 File Name …