单行道

shshsh_0510 · 发表于 2008-6-16 11:30:08

这题感觉对较大的n很难算，搜索空间太大了$O(2^(n^2))$
对于一给定的有向图的检测，大体相当于Google的pangrank中求sink，可以参照他的算法。

无心人 · 发表于 2008-6-16 11:31:14

解检验原则
对点编号1 -- N^2
假设点，编号A
如果小于A的点到其他点有解
则只要A到A - 1，有解
则A到其他点就有解

gxqcn · 发表于 2008-6-16 11:33:24

咱们两个连举的反例都很类似

无心人 · 发表于 2008-6-16 11:41:38

注意
搜索存在优化的

首先图要满足一笔画条件的

shshsh_0510 · 发表于 2008-6-16 11:46:48

别老“一笔画”，这个应该是“强连通“有向图

无心人 · 发表于 2008-6-16 11:48:27

俺是白菜
不懂图论阿

哈哈

mathe · 发表于 2008-6-16 11:52:07

如下图，下面的图强连通（也就是任何两点之间存在有向路径），
但是里面不存在哈密顿回路（也就是经过所有点的回路），所以无心人的想法也不可行

无心人 · 发表于 2008-6-16 11:56:15

看来3的解多了很多阿

用检验规则作呢？
首先构造点1的，再点2，再点3
除了1
后面的点
只要保证点N到N-1，
依次类推，就能得到全部解吧

＝＝＝＝＝＝＝＝＝＝＝＝＝＝
上午光Build linux Kernel 了
哈哈
reboot检验内核去了

shshsh_0510 · 发表于 2008-6-16 12:07:08

检验是否强连通是容易的，我记得好像是“算法导论”，有一个强连通分解算法，好像是用两次深度优先，所以是O(2(m+n))的

mathe · 发表于 2008-6-16 12:08:35

是的，时间复杂度同拓扑排序相同，都是线性时间复杂度。

账号		自动登录	找回密码
密码			欢迎注册

[擂台] 单行道