75 条题解
-
0
lemon_cn LV 3 @ 16 年前
O(n)的dfs+RMQ就行,试试pku上的加强版...
-
-18 年前@
floyd:
-
-116 年前@
一年后终于AC了。
-
-116 年前@
一年后,迟来的ac...
-
-116 年前@
怎么办啊
此题完全看不懂 -
-116 年前@
为什么我N^3次 全部0MS过?
莫非常数优化的好? -
-116 年前@
应该可以从中点扩展核以缩短时间
-
-116 年前@
一次AC
这个题啊…………
初次做这种题,好难啊^^
我做了一下午,不过终于是一次AC了……我的方法:
先读入数据,用邻接表存(数组模拟),
在用dfs求出任意两点间的距离(正常情况下是O(2^n),但谁让他是一棵树呢,现在是O(n))
再用n^2时间找到直径(用回溯找路径),
在在直径上枚举所有可能的核(这个简单,但我想了很久,下标极容易错),
每次枚举时dfs计算(O(n))就可以了…………好爽啊,这个题沉了一年了终于做出来了…………
-
-116 年前@
可以做到O(n)的呢,用队列优化的动态规划,我就这么过了。
预处理貌似比较麻烦。 -
-116 年前@
以下数据4组是该系统的测评数据
17 1
1 2 5
2 3 3
2 4 3
4 5 2
4 6 5
5 17 1
6 7 3
6 11 4
7 8 3
7 9 6
7 10 3
11 12 3
11 13 2
13 14 1
13 15 3
13 16 1ANS:13
5 46
1 2 5
1 3 15
1 5 6
2 4 28ANS:15
8 6
1 3 2
2 3 3
3 4 6
4 5 8
4 6 5
4 7 2
7 8 4ANS:8
16 11
1 4 4
4 8 3
4 5 3
5 9 2
9 10 1
5 6 5
6 11 4
11 12 2
12 13 1
12 2 2
11 14 3
6 7 3
7 15 3
7 16 3
7 3 5ANS:8
5 1
1 2 5
2 5 5
2 3 5
2 4 5ANS:5
-
-116 年前@
奶奶的,终于过了
我记得原题里N -
-116 年前@
第9个超时,- =
-
-116 年前@
看不懂啊!
-
-116 年前@
靠- -
居然没数据.. -
-116 年前@
去年就挂这题上了啊 再做次吧