非常荣幸今年能够有机会为这样一个大规模的程序设计竞赛出题，在全国为数众多的OIers和ACMers面前献丑，也实属鼓足了勇气，万幸的是整个比赛比较平静，看各个论坛和群也没有人指责我题目的问题，算是得到了些许安慰。

我计划本篇报告一共分成三次来写，第一和二部分分别是B和C的详细算法，第三部分是我关于这次题目在出题过程中的一个简单总结，或者叫花絮，希望愿意读的朋友来捧场。

好了，先来看看题目。B题的原文描述如下：

现在，麻烦来了，T公司要在全国n（1<=n<=10,000）个城市中架设服务器，以提高其网络服务质量。但由于资金限制，我们只能选择其中P（1<=p<=50且p<=n）个城市作为服务中心，其余的城市需要由这P个城市中的一个来提供服务。如何选择这P个城市并提高通讯质量难倒了一批又一批的工程师。
好在，传闻Richard是这方面的专家，于是T特聘他来帮忙解决问题。果然，Richard到了公司后就开始大展拳脚。首先，对于城市A，如何快速的求出应该把哪个城市的服务器分配给它？这个问题至关重要，因为用户并不希望等待过长时间才开始使用服务。
你的方法是通过考虑每个城市服务器的特点，然后将每个城市表示为一个整数（32位有符号整数范围）。对于城市A，我们表示为network(A)。那么，谁来为A提供服务？令对任意城市x，value(A)=abs(network(x)-network(A))（其中abs为取绝对值），那么，我们说为A提供服务的城市应该是使得value(A)最小的一个（如果有多个，则任意选一个）。这一步处理工作完毕后，剩下的工作是如何找到这P个安放服务器的城市。为了达到最好的服务质量，这样的安排需要满足所有城市的value总和最小。
这个问题难倒了Richard。为了拿到工钱（更重要的是保住其专家的称号），他决定不惜重金悬赏求解这个问题。聪明的你，还不快来试试？

其实这就是IOI2000经典问题Post Office的升级版。很多人可能都看过毛子青的那篇经典的将动态规划优化的论文，但惟独一个遗憾是他那篇文章在分析用四边形不等式优化该问题时最后得到的复杂度结论有错，那个算法应该是O(n^2)的复杂度而非O(np)，这也是为什么很多人吃了TLE的原因。

其实，更早有一篇IOI集训队论文就已经讲到了一个非常优美的算法，不过那篇文章非常简短，所以很多人可能没有在意。我标程的算法其实就是那个，在这篇报告中我稍微详细的讲讲。

首先对所有数据进行排序，这步证明很基本，反证得之，略过。然后列出基本的DP方程：f(k, j) = f(k-1, i-1) + W(i, j)。其中，f(k,j)表示从前j个城市中选择k个作为服务中心的最小开销，W(i,j)表示从数据排行第i的城市至第j的城市中选取一个作为服务中心的最小代价。假设排序后的数据存放在X中。

下面首先证明一个性质：使得W(i,j)最小的城市一定是第(i+j)/2个。假设P(k)表示选取第k个城市作为中心，如果k < (i+j)/2，那么有：

P(k+1) = P(k) + (k+1-i)*( X(k+1) – X(k) ) – (j-k)*( X(k+1) – X(k) )

= P(k) + (k*2+1-i-j)*( X(k+1) – X(k) )

因为 k < (i+j)/2，所以有k ≤ (i+j)/2 – 1，就有(k*2+1-i-j) < 0。因此得到P(k+1) < P(k)。同理，当k > (i+j)/2时也可以如法炮制的证明。于是原命题得证。

接着我们来回顾一下所谓的Convex Monge Condition，也就是常说的四边形不等式。仍然用上面的W来描述，就是：

W(a,c) + W(b,d) ≤ W(b,c) + W(a,d)，对所有的a < b 且 c < d成立。

接着介绍的另外一个很类似的概念：Convex Totally Monotone，中文叫凸完全单调性。定义如下：

W(a,c) ≥ W(b,c) => W(a,d) ≥ W(b,d)，对所有的a < b且c < d都成立，其中=>是逻辑蕴含的意思。

这个东西有什么神奇的性质呢？来看两个：

1. 假设W是个n行m列的矩阵（以后都这么说），设Ri表示第i列的所有元素的最小值所在的行。那么有R1<=R2<=R3…<=Rm；

2. 四边形不等式能推导出凸完全单调性，但是反之则不然。

我现在要说是，这个题目中的W满足这个凸完全单调性吗？或者更甚，满足四边形不等式吗？这两个问题的答案都是肯定的。那么如何证明呢？因为后一个命题的更强，所以我们只需要证明满足四边形不等式就好，可以通过两步证明：

1. 对所有的i ≤ p ≤ j，有W(i, j+1)-W(i, j) ≥ W(p, j+1)-W(p, j)。

2. 将上式中的i和p替换为a和b，然后将j替换为所有区间[c,d]间的数，于是得到d-c+1个不等式，把它们加起来就可以得到答案。

下面就利用这个性质来设计高效算法。

回顾刚才的基本方程：f(k, j) = f(k-1, i-1) + W(i, j)。当k固定的时候，我们需要枚举i和j，在naïve算法中这是个O(n^2)的过程。假设矩阵B(i, j) = f(k-1, i-1) + W(i, j)，其中k ≤ i ≤ j，那f(k, j)其实就是B的第j列的最小元。因此，我们的目标就是加快求出B的所有列的最小元。

首先可以证明，当W满足四边形不等式时，B也满足。自然，B也同时满足凸完全单调性。我们用一个三元组（start, end, r）表示在[start, end]间的所有列的最小元在第r行上。算法开始时，我们只有一个元组(k, n, k)，即当我们只考虑了第k行的元素时，所有列的最小元都在第k行。接下来我们一次考虑第k+1, k+2……行。设当前考虑第p行，那么我们的工作就是在最快的时间内找到一个t，当所关心的列 ≥ t时，我们有他们第最小元在第p行。

首先，我们用一个队列维持当前的所有元组，并且满足下一个元组的start是上一个的end+1，即列的区间维持一个升序。然后初始化t = n+1，然后从最后一个元组开始考虑，那么只有三种情况：

1. 当B(end, p) ≥ B(end, r)时，我们知道对所有的c < end，有B(c, p) ≥ B(c, r)。这个就是凸单调性的逆否命题。这时我们不需要再向前扫描了；

2. 当B(start, r) ≥ B(start, p)时，根据凸单调性，对所有的c > start，有B(c, r) ≥ B(c, p)。这时我们知道该元组已经作废了，因为[star, end]中的所有列的最小元都不在r，至少有p就比它们小。于是弹出改元组，继续向前扫描；

3. 第三种情况就是，在[start, end]中存在一个t，使得对所有c ≥ t，有B(c, r) ≥ B(c, p)。如何来找这个t呢？通过二分查找就可以轻松的确定。这时也不需要再继续向前扫描。

然后我们就得到了这么一个t。如果t < n + 1的话，我们就加入一个元组( t, n, p)，否则就什么都不干。当最后一行n都计算完毕后，此时我们在队列中就维护者我们之前想要计算的答案：对于B的每一列，它的最小元在哪一行。

通过均摊分析，我们发现整个计算过程是O(nlgn)的复杂度。当然，B一共需要求P次，所以总的复杂度是O(Pnlgn)。

具体实现还是有好多需要考虑的细节，大家自由发挥。如果愿意的话，可以向我提出挑战我的程序（如果你有更好的算法，希望你能告诉我，因为我知道传说中好像真的有一个O(nP)的算法存在，只是我能力有限未能搞明白），然后咱们一边去晒晒，^_^。

这篇就到此为止，本题的数据和参考代码可以跟我发邮件（frogxx@gmail.com）索取。下一篇讲C 题。说实话，其实我更喜欢C一些，因为solution所需要的知识非常简单，只是中间的模型变化不容易想到，而B是如果没学过相关知识，从头到尾都不容易想。貌似比赛中C没有被人做掉，这点我还是有一些遗憾，希望大家能再想想。

先离题，我觉得有必要先定义难和易的概念。

有些题目，它可能要经过好几步的模型转换，而且每一步的处理都需要一些比较高深的算法，比如网络流，自动机等。但是，其中的每一步的转化非常的straight forward，或者说用一些很普通的处理手段就可以看出解决方法。这类的题目非常多，特别是POJ月赛中。但我认为它们并不能算真正意义上的难题，能够做出不值得骄傲。

还有些问题，可能解决方法非常简单，代码量也非常小，但是却需要打破常规思路才能得到答案。我觉得就是要做这类题目，才可能在思维上有质的飞跃。

最近的两场SRM（423和424）就出现了两道我觉得值得一提的题目，下面介绍一下。

第一道题目是300pts。一个无限大的棋盘上放了n (n<=50) 个棋子，初始是任意的放置，所以也可能有位置相同的。问题是，最少移动多少步可以使得至少K个棋子在同一个位置上？其中从A移动到B的步数是两者的曼哈顿距离。

有一个很简单的问题我们或许都知道其答案：将n个棋子放在一起最少需要多少步移动？由于曼哈顿距离的特点，我们可以分开算X坐标和Y坐标。最后所有棋子移动到的点的X坐标一定是它们初始坐标排序后的中位数，Y坐标同理。因此，我们可以在O(n)的时间内解决将所有棋子移动到一起的问题。

现在考虑K<n。显然，普通的做法就是在n个中枚举K个棋子，然后用上面的方法计算移动步数。这样做的复杂度是O(C(n,k)*n)，显然不能接受。那么，如何优化？其实很简单，就是将这个不可接受的算法的计算顺序颠倒一下。仔细想想，由于X和Y坐标都是取中位数，也就是说最终要移动到的位置的X和Y的坐标是可以从已知的这n个点中组合出来的！因此，n个点最多有n^2个候选的位置，而对于选出的目标位置，很显然就是是n个点中离它最近的K个移动到一起。因此，通过简单的调换计算顺序避免了大量重复计算，将复杂度降为O(n^2KlgK)。

其实，这个算法也体现了动态规划思想的精髓：避免重复计算。然而，上面看似简单的算法，却非常不容易想到，原因就是我们先入为主的思想在作祟。

另外一个是600pts的题目。你在玩一个冒险游戏，现在有n个关卡。要通过一个关卡，玩家的当前智商和力量的值至少有一个要大于等于该关卡的限制。每通过一关，可以得到一些分数，你可以将这些分数任意的分配到你的智商和力量的属性上。初始你的智商和力量都为1，请问，如果通关的顺序没有要求，请问你最多能通过多少关？其中，关卡的属性值限制<=1000，n<=50。

初看真没什么想法，那就枚举吧。先枚举出通关的顺序，然后再求解这个顺序下最多能通多少关，复杂度是O(n!*n)。想基于这个思路动规，好啊，那总得状态压缩一下吧，答案是O(1000*1000*n*2^n)，没觉得这个方法有多好，怎么办？

其实，第一题的优化已经提示我们，盲目的枚举必然隐藏了大量的重复计算。回顾一下，第一题的重复计算在哪里？其实就在于，虽然一共有C(n,K)种点的组合，但是它们却一共只有O(n^2)中不同的最终集合位置。形式化一点，就是这指数阶的组合方案它们的某一个性质一共只有多项式阶种。回到这道题，其实就是所有通关顺序得到的最后的智商和力量属性的组合最多只有1000^2种（去掉>1000的情况，因为1000已经是所有关卡要求的上限）！

那么依葫芦画瓢，先枚举一种属性组合，然后再求出能得到这个属性组合的最优通关序列。很快发现，这样的话，不直接枚举(1000,1000)就可以通过所有关卡了？所以，再这一思路上，我们还应该多做些限制才好。

那么，为什么不能枚举(1000,1000)呢？原因就是这个组合或许根本就不存在。而题目一中不做这个处理的原因是，虽然有些位置不可能作为最终位置，但是计算它们不会影响最后答案。那如何快速判断哪些状态是可能出现的呢？

设状态(x,y)是可达的，则(x,y)必然是由某一个可达状态(x’,y’)通关后得到P分生成的（注意，假设P可以不用全部分配。因为这一假设不影响最后的答案，所以它是可行假设）。因此，很容易想到可以通过广度优先的过程从(1,1)开始，每次检测该状态能通过的所有关卡能得到的总分数，然后把剩余分数，即left=y+x-2分配后求得其它的可行状态。

答案很明显了，不再多说。

再总结一下这两道题目的特点。它们将一个具有指数阶以上定义域的问题转化到只有多项式阶的状态空间中，再在此状态空间中设计算法以得到原问题的最优解。我们可以看到，上面的算法的都不难证明，而且代码也容易写就，难就难在如何转化问题的状态空间。我觉得，只有多做这样的题目，才能迅速成长。

最后，即使你实现上面的算法很容易，也请抽空看看楼教主的代码，非常漂亮。

题目的链接放在文末，大家可以试试再来看本文。

简述一下题意，就是有n个人，站成一个圈。每个人开枪击中别人的概率是固定的（设数组P[i]表示第i个人的命中率），从第一个人开始轮流开枪，求每个人生还的概率是多少？（假设每人都以最有利自己的方式选择射击对象，并且当有多个目标都一样好时，随机选择其中一个。并且，每轮都必须射击，虽然故意放弃射击机会可能增大存活的概率）。

一个引导我们想到方法的条件是，n <= 13且时限是4s，这提示我们这道题不像是个推数学公式的题目，并且很有可能是状态空间递推相关的方法。说到状态空间，必然就要设计状态的表示。直觉告诉我，状态表示是带集合的（因为n太小了），因此设计状态F[a][b][S]，表示当S集合的人一起玩这个游戏，并且下一个开枪的人是b时，a最终胜出的概率。

再来研究状态转移。如果a == b，那么显然b不会射击a（不允许自杀=.=），于是选择一个射杀后最大概率使a存活的人，设为c，于是有T = S ^ ( 1 << c )。再计算到c死后下一个射击的player为d，于是转移到F[a][d][T]，由此可得hit(a,b,S) = P[b] * F[a][d][T]；

另外，如果a != b，情况就不容乐观了。因为b为了使自己生存的几率更大，是可能选择射杀a的。假设现在有m个b中意的（何为中意？即射杀后b生还的概率最大）射杀对象（a是否是一员不用特设处理），对于对象k，设射杀后下一个射击的人是kk，集合变为T(k) = S ^ ( 1 << k )，于是转移到F[a][kk][T(k)]。最终有公式hit(a,b,S) = sum( F[a][kk][T[k]], for all k ) / m。

更有趣的是，如果b没有击中他想要击毙的人，怎么办呢？此时，状态集合S没有变，改轮到下一个人c射击了，于是转移到F[a][c][S]，有miss(a,b,S) = ( 1 – P[b] ) * F[a][c][S]。再进一步，如果S中的人射击完这一轮后，都没有命中，是不是又该轮到b射击了，也就是说，这里状态图出现了循环依赖，因此不能直接DP。

要解决循环依赖，其实也不难，假设现在集合中S有三个人a,b,c，从a开始射击，把方程列出来看看：

F[a][a][S] = hit(a,a,S) + ( 1 – P[a] ) * F[a][b][S]

F[a][b][S] = hit(a,b,S) + (1 – P[b] ) * F[a][c][S]

F[a][c][S] = hit(a,c,S) + ( 1 – P[c] ) * F[a][a][S]

移项再整理一下，得：

hit(a,a,S) = F[a][a][S] – ( 1 – P[a] ) * F[a][b][S]

hit(a,b,S) = F[a][b][S] – (1 – P[b] ) * F[a][c][S]

hit(a,c,S) = F[a][c][S] – ( 1 – P[c] ) * F[a][a][S]

这便是一个标准的常系数非齐次线性方程组，用高斯消元解决之。可以证明这个系数矩阵是可逆的，因此它有唯一解。还有一个小优化（其实狠重要的优化）是这个系数矩阵是比较特殊的，据此可以把GE跑到O(n)。

对于每个人x，最后的答案就是F[x][0][(1 << n) – 1 ]。

其实，写此文，我还有一个目的，就是我自知这个方法不是很优秀，特别是上述对于循环依赖的处理，疑有数学方法，或者，还有其它更好的状态表示就能自身解决这个问题，所以希望大家回复赐教，不胜感激。

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=3028

我从来没有把数论搞清楚过，自然我从来没有写过相关的东西，而今天这篇文章也不过是在网上看到类似帖子而受到启发而作，但总算是解决了我心中的又一个疑问。

当谈到到和Burnside引理相关的问题，稍有档次的题目便会涉及到一些数论变换，而下面这个问题便可能出现：

求 (a / b) mod n ，其中b | a。

如果是a+b或者a*b，我们便再熟悉不过了，但是现在偏偏是a/b。首先要注意到，我们的运算是基于整数的，而整数对于除法不封闭，即不能作为代数域，自然就不能理所当然的把方法推广到(a/b) mod n = ((a mod n ) / ( b mod n )) mod n。不过，上式变换为((a mod n ) * (1/b mod n)) mod n 是可行的，于是我们现在的目标就是求1/b mod n。

好了，好端端的式子现在变形为非常奇怪的问题，现在继续变：

设答案为x，则原式：

((b mod n) * (1/b mod n)) mod n = ( x * (b mod n) ) mod n

=> b * x = 1 ( mod n )

恩，这个就是我们再熟悉不过的模线性方程了，其有解的充要条件是 gcd( b, n ) = 1, 于是用扩展Eculid求出x，上面那个奇怪的方程的答案也就找到了。

现在的问题是，如果gcd(b,n) > 1怎么办？必须要说明的是，这时我们求不出后面分离a后的1/b mod n的值，但是不代表原来的式子求不出来（哪里有求不到答案的取余操作呢？），这个时候还不用老老实实的去算a和b的值，一般来说有以下办法可以尝试一下：

1. 如果a有一个约数是gcd( b, n )， 约掉它于是问题就归约为上面所述了；
   <!– @page { size: 21cm 29.7cm; margin: 2cm } P { margin-bottom: 0.2

2. a / b一定有一种比较简单的方法求得，看看之前的步骤是否少用了一些资源。

那上面绕了个大弯子的方法有什么用？最大的好处是避免了高精度运算，比如下式：

( A! / (a! * b! * c! * d! … ) ) mod n

如果n 和 a, b, c, d…全部都互素，那就简单了，把所有的(1/ a!) mod n, (1/b!) mod n都求出来，然后作一个乘法就搞定了，是不是很简单？

前天南京赛区比赛的A题，我没能在比赛中写出来，确实很遗憾，现在总结一下，希望下次能封杀这种类型的题。

还是先回顾一下题目，免得以后找不到了。

给定一个长N的序列，那么该序列可以生成N(N-1)/2个子序列。如果将所有这些子序列排序，那么请找出第K大的一个来。

拿到那种一眼之下毫无思绪的题时，应该马上想到从答案入手解决问题。再仔细一看，答案其实是满足单调性的（如果guess是合法答案，所有小于guess的数一定不是答案），一种非常高效又常见的思路就是二分枚举答案然后再验证，好了，框架有了，下面就看如何来验证。

首先，对输入的序列A求部分和，S[i]=A[1]+A[2]+……+A[i]，假设当前的答案为guess。

其次，需要明确一个基本道理，所有的子序列都可以由S[i]-S[j]（1<=j<=i<=n）得到。

1． 利用归并排序

设当前待排序的区间为 [l,r]；

令mid=(l+r)/2；

设某子序列的起始位置分别B,E。

因此，该区间存在的所有序列只有三种情况：

A． B和E均小于等于mid；

B． B和E均大于mid；

C． B小于等于mid，E大于mid。

前两种在“分”的时候就统计出来了，我们只考虑情况三，即“治”的过程。

我们枚举任意的E，那么对任意的B，如果有S[E]-S[B]<=guess，那么所有的B<=i<=mid均满足S[E]-S[i]<=guess。由于前半区间已经排序，因此直接二分得到最靠前的B。

这样，统计就结束了，但别忘了归并排序还没开始。

总复杂度O(lgINT_MAX*n*lgn)。

问题就这样解决了，但是还有没有更快的方法呢？

2． 利用树状数组

换一个思路，统计以位置i结尾的所有子序列中小于等于guess的个数，数学描述为：

S[i]-S[j]<=guess，其中0<=j<i。

移项，S[i]-guess<=S[j]，因此问题变成了统计有多少个j满足上述条件，j=0的情况需要单独处理。

既然用树状数组，那么就先离散化，把S做一个索引排序，这样就使得S有序了，便于后面的二分查找。

此过程文字不好说明，用代码表达好了：

For i=1 to n do

j=find(S[i]-guess)； // 假如存在S[i]-guess，得到它该在的最靠后的位置

rank+=S[i]<=guess； // 特殊处理j=0的情况，因为Tree Array不能处理

rank+=tree_down(n)-tree_down(j-1) // 得到j

tree_up(id[i]) // id[i]是离散化后S[i]的排名

End

中间的tree_down和tree_up是Tree Array的向上和向下过程，就不写了。

复杂度O(lgINT_MAX*nlgn)，与一相同。

方法二在实际中的速度要快很多，可能是因为Tree Array很简洁的原因。

好了，肯定还有其它的方法，但基本上都大同小异，这里就不再继续举例了。

另外，POJ上的2104和该题的思想很接近，估计出题者是借鉴了该题的，但是为什么当时比赛的时候没想到呢？？

8月份的进度相对缓慢许多,主要是把以前的遗漏给补上,并学习一些新的东西.9月我准备做一些提高性的尝试,为区域赛作准备.

我打算总结下以下几个算法或几类问题:

1、最小树形图的算法和应用;

2 、2-SAT问题的相关内容；

3、线性代数的一些东西；

4、计算几何，主要是平面几何的内容；

5、后缀数组和字符串的处理；

6、网络流，最小费用流模型的理解和运用；

7、DP的优化，好象目前水平还不高，回来再看看;

8、burnside引理和polya定理。

好了，就学了差不多这么多吧，感觉学得都很水，但是总结的时候希望理解上提高一个档次。

比赛完了听LiuXin说了解法，不过当时他描述得异常复杂，吓得我很久都不敢碰它。曾经花了个下午研究标程，但是无果而终。

今天终于搞明白了，如果当时想到用图来分析问题，那可能问题早解决了。。

分析过程如下：

1、首先，一个脏点不会被改变两次或多或少以上状态；

证明: 如果不停扫某行或某列这显然是没有意义的，所以只能是行列一起打扫，且都只被打扫最多一次，而如果两者同时打扫也没意义，所以只能扫一次。

2、将行和列抽象成图的顶点，一共有2n个。如果某行和列的交叉处是一个脏点，那么在它们间连接一条无向边，那么最后可以形成若干个双连通分量，它们可以分别对待；

3、取任意分量，我们对它的顶点0-1标号，以保证任意边两边的顶点的标号异或为1。因为是二分图，所以着总是可以做到的，并且可以发现要么所有代表行的点为1，要么列为1，说明完全清扫一个连通分量只可能要么全部打扫行要么全部打扫列；

4、根据以上原理，统计每个分量中行点和列点的个数，取小者并把所有的分量相加就是答案。

这题确实出得不错，它不能直接用二分图匹配来做，原因是脏的还要变回来，但最后还是用二分图巧妙的解决问题，值得我们思考。

本题连接： http://cs.scu.edu.cn/soj/problem.action?id=2662

前天在FZU做题，其中的C和D都和BST有关，觉得题目出得很好，其中C我想的方法我觉得有必要记录下。

不过我不想重复题目，于是提出以下问题：

能否直接通过BST关键字的插入顺序不建树构造出该BST的前序遍历结果？

答案是肯定的，算法是基于以下基本属性设计：

BST中任一节点i的左右儿子分别是插入序列中排在i之后最先的小于i和大于i的数。

上面的性质很显然，然后我们再利用中序遍历的优美性质，即在中序序列中在i左边和右边的数分别是i的左右子树上的点，可设计以下算法：

1、将插入序列用索引进行排序；

2、对排序结果进行RMQ算法的必要预处理（如ST算法）；

3、递归处理上面的排序序列：（初始l=1,r=n）

1、查找[l,r]区间内值最小元素所在的位置，如p；

2、输出p元素所代表的在插入序列中的真实值；

3、递归处理[l,p-1]和[p+1,r]。

下面举例来说明：

设插入序列为（数组名为A）：8 3 10  14 13 6 1 4 7

索引排序结果为: 7 2 8 6 9 1 3 5 4

找[1,9]中的最小元素为1，在位置6，输出A[1]；

分别处理[1,5]和[7,9]，此处省略1000字……

最后结果为: 8 3 1 6 4 7 10 14 13

算法复杂度O(nlgn）。

但我不知道有没有线形算法，感觉上没有，因为否则的话就可以逆向证明基于比较的排序算法复杂度下限为O(n)，显然不成立。

应该是经典问题了，今年XMU以及99年的CEOI都出现了这个问题，这是前者给出的是有向图后者是无向图，如果不考虑搜索策略的话，是没有区别的。

解决这个问题的办法是利用floyd算法。我先说算法然后再证明。

算法：

设原图的邻接矩阵为D[N][N]，松弛中的为F[N][N]。

枚举一个圈上相邻的(这三个字很关键)三个点，比如说顺次是i、j、k，需要满足的条件是j的编号是除i、k外这个圈上最大的。因此其中有一种解就是ans=D[i][j]+D[j][k]+F[k][i]。

为什么是这样呢？想想floyd松弛的过程。根据松弛的方法我们知道i、j的最短路可以由一个中间结点k来变得更短，而k是从小变化到大的，所以每次我们枚举的那个最大点j一定不会出现在k->i的最短路中,而我们知道k->i的最短路是简单的,所以可以证明我们已经考察了图中所有的简单圈。

算法并不复杂，但要想对也很不容易。XMU那题当日比赛的时候我过的是一个错误的程序，后来有同学给我指出。于是又想了个写法，结果昨天发现还是错的。这次终于没有问题了，所以我把XMU那道Lightest Cyle的代码放出来：

#define INF 0x7fffffff

#define N 128

int f[N][N],D[N][N];

int n,m;

void input()

{

    int i,j;

    int a,b,v;

    for (i = 0; i < n; ++i)

        for (j = 0; j < n; ++j) f[i][j] = INF;

    for (i = 0; i < m; ++i) {

        scanf("%d %d %d",&a, &b, &v);

        if (a == b) continue;

        if ( v < f[a][b] ) f[a][b] = v;

    }

}

void solve()

{

    int i, j, k;

    int ans, t;

    if (n < 3) {

        printf("-1n");

        return;

    }

    ans=INF;

    memcpy(D,f,sizeof(f));

    for (i = 0; i < n; ++i)

        for (j = 0; j < n; ++j) {

            if (j==i) continue;

            for (k = 0; k < n; ++k) {

                if (k == i || k == j) continue;

                if (f[k][j] < INF && D[j][i] < INF && D[i][k] < INF ) {

                    t = f[k][j] + D[j][i] + D[i][k];

                    if ( ans > t ) ans = t;

                }

            }

            for (j = 0; j < n; ++j) {

                if (j == i || f[j][i] == INF) continue;

                for ( k = 0; k < n; ++k) {

                    if (k==i || k==j || f[i][k]==INF) continue;

                    t = f[j][i] + f[i][k];

                    if ( f[j][k] > t ) f[j][k] = t;

                }

            }

        }

    printf("%dn", ans == INF ? -1 : ans);

}

int main()

{

    scanf("%d %d",&n, &m);

    input();

    solve();

    return 0;

}

[/code]