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 …

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） 思路：二分图最佳匹配，KM算法，2A. /* …

hdu 2426 题目链接 题意：n个学生，m个宿舍，每个学生住一个宿舍，然后n个学生给若干个宿舍打分，分数可正可0可负，学生不能住打的分为负的宿舍，或者没有打分的宿舍。问在满足上述条件的前提下，所有学生住的宿舍的分数之和最大是多少。如果无解输出-1. 思路：二分图最佳匹配。。。读漏题QAQ. 原来分数为负的房间是不能住的啊。。。。 考虑无解的情况，如果学生数比宿舍数多，无解。 如果一个学生不喜欢任何宿舍或者没给任何宿舍打分，无解。 然后KM. /* *********************************************** Author :111qqz Created Time :2016年06月01 …

hdu 1533 题目链接 题意：给出一个n*m的maze，其中包含不超过一个人（用m表示），以及和人数相等的房子（用H表示），其他都是‘.’，表示可以经过的路径。人向一个方向移动花费代价1.问每个人都回到一个房子里的最小代价是多少。ps:每个格子是无限大的，也就是所有人可以同时踩在一个格子里。以及：路过一个房子可以不住，而只是“经过”。 思路：有了那两个条件，这题就是赤裸的二分图最优匹配了。建图也很easy.可以预处理下w,就是两点的哈密顿距离. 需要注意的是这道题求的是最小权值。那么做法就是将w取负，然后答案再次取负即可。 （还有其他方法处理，不过这种最easy应该？） （不过要保证初始化某些数组的时候要比所有的值小，所以不能 …