85 条题解

  • 0
    @ 2008-10-17 11:59:43

    DFS 也可以.

    推荐SPFA 练练手.

    第八组数据有错?

  • 0
    @ 2008-10-17 11:00:48

    用DFS!!!很简单 也不长

  • 0
    @ 2008-09-23 10:26:46

    囧~

    1和5 WA了~

    总长度一样的,只是和答案输出的路不同~

  • 0
    @ 2008-09-19 09:08:27

    无语第8组数据,竟然存在环。

    无奈的CHEAT之...

    编译通过...├ 测试数据 01:答案正确... 0ms├ 测试数据 02:答案正确... 0ms├ 测试数据 03:答案正确... 0ms├ 测试数据 04:答案正确... 0ms├ 测试数据 05:答案正确... 0ms├ 测试数据 06:答案正确... 0ms├ 测试数据 07:答案正确... 0ms├ 测试数据 08:答案错误...程序输出比正确答案长├ 测试数据 09:答案正确... 0ms├ 测试数据 10:答案正确... 0ms-------------------------Unaccepted 有效得分:90 有效耗时:0ms

    Then...

    编译通过...├ 测试数据 01:答案正确... 0ms├ 测试数据 02:答案正确... 0ms├ 测试数据 03:答案正确... 0ms├ 测试数据 04:答案正确... 0ms├ 测试数据 05:答案正确... 0ms├ 测试数据 06:答案正确... 0ms├ 测试数据 07:答案正确... 0ms├ 测试数据 08:答案正确... 0ms├ 测试数据 09:答案正确... 0ms├ 测试数据 10:答案正确... 0ms-------------------------Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2008-09-11 00:05:38

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    我用的spfa,修改了一下,求最长路径。显然不像楼下的说的那样需要两次spfa,我只用了1次,然后dfs找路径。写了近80行。

    ms这题用关键路径更好写,需要学习一下了.^_^

  • 0
    @ 2008-09-09 20:02:13

    为什么总是不能ac

    用搜索的办法,

    吧 谁能告诉我

  • 0
    @ 2008-08-16 00:16:06

    终于明白了,

    第二问求的不是一条关键路径上的点,

    是所有最长路径上的点……

    搜一下就可以了

  • 0
    @ 2008-08-14 04:14:46

    我不知是我理解有误还是如何。

    确实要像楼下下下……的同学那样SPFA(BellmanFord)两次才行。

    否则只能得到80分。

    不过感觉这样仍旧不完备,甚至是个错的=_=bb...

    例如:

    4 6

    1 2 1

    2 5 1

    1 3 1

    3 5 1

    1 4 1

    4 5 1

    应该是

    2

    1 2 3 4 5

    如果spfa两次的话是

    1 2 4 5.

    所以本题不适合用spfa..=_=

  • 0
    @ 2007-11-15 13:22:14

    无语,第8组就是过不了

  • 0
    @ 2007-10-21 11:49:49

    坚持到现在不容易啊,好歹抢到了第一百个.

    虽然本人向来不喜欢cheat..但是,为了上榜这个荣誉,霍出去了.

    怪怪的这题目.算法实在应该没错什么啊.

    VIJOS现在又故作高级,不让骗数据,还真不知道错在哪里.

    就这样吧,坚持不下去了....

  • 0
    @ 2007-10-20 10:57:08

    哎,花了我3个小时,结果写了个搜索过了...程序40来行也...

  • 0
    @ 2007-10-17 15:49:21

    什么叫关键路径?

    如果这题 起点为1---|-5 中间尽量多找点。。。。

    意思就是找最大环, 如果有几个同样大的环,那么比较权值,是这样吗?

  • 0
    @ 2007-08-28 11:01:54

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    拓扑排序+关键路径

    CHEAT第8组数据 总觉得第8组数据有错。。。

  • 0
    @ 2007-08-04 16:20:47

    有没有人可以解释一下样例?

  • 0
    @ 2007-08-02 11:03:34

    图里面没有圈!我用深搜提交了一遍!

    那就是纯粹的求关键路径了,那我怎么会WA第8点。。。。。太奇怪恶劣。

  • 0
    @ 2007-07-16 14:37:50

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    Bellman-Ford可以求负权最短路径,,同样方法也可以求正权最长路径,,但是最好求两次,,1次是如果找到1条路径长于当前以求路径的时候更改,,另1次是当如果找到1条路径不短于当前以求路径的时候更改,,把两次都经过的点存起来再排序输出(我是用f[1..101]:boolean来记录该点需不需要经过..)

  • 0
    @ 2007-06-08 13:36:06

    重在题意不在程序~

    注意理解“要经过的所有可能的剧情结束点(按升序输出)。”

    就是要你把可能经过的点纪录下来 然后排序输出(不能有重复)

    怎么实现大家自己去想

    而且如果直接拓扑排序第8个点会有问题

    这题规定任务节点1是初始点(即使1也存在入度)

  • 0
    @ 2007-03-19 13:01:45

    第八组数据是什么!!!

  • 0
    @ 2007-01-13 22:25:13

    ms图中存在环阿,怎么处理?不是dag了还能求关键路径?

  • 0
    @ 2006-11-11 10:05:04

    对于关键路径来说,一定有不同的条数,所以,输出的那一条,肯定是随机的……

    所以,AC有点靠RP。

信息

ID
1027
难度
4
分类
图结构 点击显示
标签
(无)
递交数
1489
已通过
604
通过率
41%
被复制
13
上传者