第一次看了理论之后自己敲代码直接 1A ！！！蛤蛤蛤蛤！！！ 嗝～～ 稳定婚姻问题的定义与求解方法详见百度百科 中文维基上写的比较简单。 简单说一下个人理解与解法。个人感觉还是挺有趣的。 稳定婚姻问题是构建在男女双方的二分图基础上的。如果对于现有的一个男女匹配，存在一个男人 a 比起现在的妻子女人 a 更喜欢 女人 b 。而与此同时，女人 b 比起现在的丈夫男人 b ，更喜欢男人 a 。那么男人 a 与 女人 b 很可能会出轨。我们称这个婚姻匹配是不稳定的。 反之，如果不存在这个会出轨的男女匹配，则称这个婚姻匹配是稳定的。 稳定婚姻问题的求法在上面的中文维基上有伪代码，我也基本上按照这个理论敲的。 略为详细的步骤如下： 1. 为每一个男性与女性确定一个各自的异性在自己眼里的排名。但是记录方式不太一样，根据我的写法，男性需要记录的是排名第几是那个女性，女性需要记录的是这个男性排第几。 2. 将每个男性加入队列。尝试为每个男性按排名配偶，如果这个女性暂时没有配偶，那么暂时进行匹配。否则，与她现在的配偶进行比较。…
01分数规划之最优比例生成树……
这道题，好坑……
一开始WA了，然后找了一个博客，WA，照着敲，WA，再照着敲，WA，索性复制再改，WA，最后复制粘贴，他的也WA了。md
感觉我写题的时候很容易石乐志，然后就很难过题……
好几场比赛都验证了……
题意：
给你一张图上的所有点，由所有点得出每条边的两个权值，欧式距离与高度差。
要你和找出一个生成树，使得 高度差的和比上欧式距离和最小。
思路：
最优比例生成树的经典题。其实只要掌握了01分数规划的思想，你就照着prime敲就好了。
我这里用了迭代法，感觉迭代法更套路一些……而且速度比较快。
#include
南大所谓的最小费用有向图………… 什么 jb 玩意？？？？不是都叫最小树形图么……………… 这道题适合Yasola一起讨论的，虽然说一起讨论，但是对权值进行修改这一关键操作还是他想得 太巨了呀！！！ 然而最后还是差一点。 题意： 给你一张有向图，要你求最大树形图，同时满足最后一个结点的父亲字典序最小。 思路： 这个朱刘算法……有毒…… 朱刘算法真的是把原图毁的不成样子…… 然后我们两个就在这里踩了很多坑…… 首先认清一点，朱刘算法是可以求负权的。这就保证了最大树形图可解。 再是单独一个结点的字典序最小。 首先一个重要的操作就是对边权扩大处理。对于指向最后一个结点的边权我们让它与父亲结点编号联系起来。 联系方法： $ edges[i].cost = v == n ? -w * 1000 – 1000 + u : -w * 1000 $ 说一下我们的很多错误思路，不想看可以直接跳过。 1. 直接用pre 数组输出。 不可行，因为结点都已经缩点染色过了，边数组的起点终点不是原起点，原终点， 2. 开一个ori 数组记录每一个染色后的点的原起…
例行废话 哇～，惊了，多校里面第一次出现网络流的题目。然而我并没有时间甚至没有看它一眼…… 我学了这么久的图论究竟是为了什么呢…… 老实说我有一种不详的预感 现在想想的确是这样的，自己努力钻研的高级算法，又有多少会在比赛中用到呢…… 回归正题 这是一道最小割+差分约束的题目，还是第一次遇到这两个结合起来。不过其实也只是分开来的问题，用差分约束判断可行性，再用最小割求解。 题意： 你要给( n) 个小朋友糖果，最少( 1)个，最多( m )个，并且你手上有无穷多的糖。并不是说给一个小朋友的糖果越多越好，给每一个小朋友不同糖果数量对应的愉悦值不同。我们自然希望小朋友的愉悦值最大化。 但这些小朋友也提出了一些要求，对于每一个要求( ( x , y , z ) )，你给 ( x) 的糖果数量 ( ax ) 与给( y) 的糖果数量( ay) 满足如下不等式 ( ax – ay \leq z )。 问满足所有要求的最大愉悦值。…
昨天晚上从Yasola那里偷来的一道题…… 为什么Yasola这么优秀啊！！！！！ 求求你别学了，我已经完全跟不上了…… 因为看着题目并不是很难我也就写了一蛤，然后自以为是无脑题就疯狂WA…… emmmm…… 其实仔细想想还是挺简单的。 题意： 给你一张无向图，要你找出最小环。 点数 ( n \leq 100 ) 思路： 对 floyd 进行简单增加一点代码。 floyd 算法剖解开来就是不断找到一个中间结点使得路径更短。而我们可以在这个中间结点加入最短路之前，将其固定为环上的一个点，这点必定不会被所有最短路夹在中间。 有一个非常显然的问题就是，当我固定一个中间结点的时候，我无法保证我所用的最短路为全局最短路。这个问题显著存在于floyd初期。 比如说 存在一个 ABCA 的环与一个 BCDB，其中 ( BD + DC < BC , AB + AC < BC )，而当我使 A 为固定结点，而我的 D 还不曾成为固定结点，也就不会被加入 BC 的最短路。 然而实际上并不要担心，…
最小割建图好题！！
昨天比赛的最小割，当时没看出来，实际上需要建图转化一下，这道题非常显然！！！
比赛后不想看题解，问了一下Yasola，指点了一下马上懂了！！
题意：
有n×m的地图，地图上最多有6个国家，现在K国要修长城，来防御敌对国家，6个国家中除了K国和一个敌对国家，其余国家都是友好国家，想要进供从而使得自己在长城防御范围内。建立长城的每一个花费都已经给出。
问最小花费。
思路：
将地图以外的地方视为敌对，将一个地图上的格子与其上下左右相连。
对于一个长城，实际上就是将K过与友好国家 与 敌对国家割开的最小割。
又因为点数和边数都很少，最多通过枚举 2^5 枚举将友好国家包围的情况，每次求一下最小割即可。
AC Code
#include
算法详解 花了一点小时间入门了 kosaraju 算法。 记得之前在一篇博文中提到过，ACM中求强联通分量的常见算法有三种： 1. 暴力 2. Tarjan 3. Kosaraju 其中暴力和 Kosaraju 算法在求强联通分量的同时，可以直接输出可行解，而Tarjan则需要通过额外的拓扑排序来得出可行解。 简单说一下 Kosaraju 的基本思路： Kosaraju算法主要通过一个非常显然的性质来求强联通分量的。 对于一个强联通分量，将它的所有边反向，那么它依然是一个强联通分量。 因此，我们通过两边dfs，第一遍dfs求出整张图的拓扑序，第二遍dfs按照拓扑序通过反向边进行拓展。 这个地方就非常巧妙。因为在按照拓扑序遍历的过程中，对于一个点，如果它是一个强联通分量的一个点，那么除开原先遍历标记过点，必然会存在拓扑序在该点之后但仍然指向该点的一个点。 好难表达，yy很容易 题解 题意： 有一群牛，给你很多个关系，一对关系 a -> b 表示 a 认为 b 是肥宅，问被所有牛公认为肥宅的牛有几头。…
第一次刷到HDU第一名，趁现在没人比我高，截图来一发！！！！ 对于这道题，我只想说一个字 妙！！！！ 题意： 给你四个点，(1,2),(2,3),(3,4),(4,1)之间都有一条无向路径，让你从 2 号点出发，最后回到2号点，同时使得走过的距离大于等于 k ，并且 最小。 k很大，最大达到 1e18 ，四条路的范围不大于 3e4 。 思路： 这道题真的是太妙了！！！ 说一下我比赛前后的思路，这里我称 从 起点 2 回到 2的回路为 E 回路。 先说一下我比赛的思路： 一开始我的思路是这样的，首先不考虑单纯的往返，那么E回路就有7种情况。 那么我考虑复杂度的话最多的就是4点成环且只有4条边的情况，对于这条已有的E回路，我们可以在任意一条路径走来回走，使得路径长度增大。 那么我们就可以将问题转化成为…