F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
大视野在线测评-欢迎您
[ New Thread ]
Problem 1880 >> 求解此题。。
Vani @ 2011-06-06 14:54:33
[ Quote ] [ Edit ] [ Delete ] 1#
很多人(包括我)都是直接在最短路图上找最长链。。
但是如下面这组数据:
8 8
1 3 2 4
1 6 1
3 8 1
2 5 1
4 7 1
5 6 1
6 7 1
7 8 1
8 5 1
答案显然是1, 按最长链的做法,结果是2
另外还有这组数据:
8 9
1 6 7 8
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
7 3 5
7 5 5
2 8 4
4 8 4
答案应该是1, 按最长链做法,结果是3

求解ing。。。
Token @ 2011-06-07 11:55:06
[ Quote ] [ Edit ] [ Delete ] 2#
没有任何问题啊……这两组数据我跑出来都是1啊……
有程序为证:http://www.ideone.com/FmugO
Vani @ 2011-06-07 20:52:14
[ Quote ] [ Edit ] [ Delete ] 3#
。。orz。
我试了T神和clj的程序, 跑出来都是2和3, 冏。。。
kang205 @ 2011-06-10 13:24:57
[ Quote ] [ Edit ] [ Delete ] 4#
我也是2和3..
kang205 @ 2011-06-10 14:30:38
[ Quote ] [ Edit ] [ Delete ] 5#
似乎是边的方向问题。

srO Token神做法
wumingshi999 @ 2017-04-05 20:48:14
[ Quote ] [ Edit ] [ Delete ] 6#
这道题可以参考Po姐的代码,Po姐的代码能跑过这两个点
calvin99 @ 2019-10-31 15:55:28
[ Quote ] [ Edit ] [ Delete ] 7#
确定第一张图的边的顺序,第二张图的边有两种情况,第一种是从S到T,第二种是从T到S,先按S到T建图,跑拓扑排序,再按T到S建图,再跑拓扑排序。如果把S到T和T到S的边同时加入图中建图跑拓扑排序会出问题。
[Top] [Previous Page] [Next Page]

HOME Back