题解 - Vijos

0

netr110 LV 3 @ 2007-11-11 16:33:11

这题的负回路一定过S点吗？`不一定吧`看了看几个发上来的程序好象都只判断了过S点的负回路。。能行吗``

0

junlonely LV 7 @ 2007-11-01 19:11:45

编译通过...

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

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

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

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

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

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

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

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

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

0

Alexandria LV 3 @ 2007-10-23 08:58:42

编译通过...

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

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

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

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

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

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

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

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

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

SPFA可解……题目巨WS……

提交** 150 / 300 题 ( 50% )** 纪念下……

0

Fallen-Angel LV 3 @ 2007-10-19 23:32:04

编译通过...

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

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

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

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

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

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

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

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

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

注意题目说的,可以不与源点连通但有负环,马甲交了N次才AC`\`

0

ChBlossom LV 3 @ 2007-10-12 10:45:40

为什么我的Bellman-Ford超时..

前六组0ms...

用SPFA就可以过了..

不过好多超过0ms 的...

0

a519522 LV 3 @ 2007-10-06 14:37:41

为什么 Bellman-Ford 在前 n-1 次迭代中不判断 d

0

海燕 LV 3 @ 2007-10-01 19:56:42

题目实在是太恶心了，需要考虑的细节太多。

首先，负权环有可能出现在与起点不连通的连通分量中，这点我考虑到了。

其次，如果有自回边的话，可能出现单节点负权回路，这点我也考虑到了。

最后，在提交一次超时的情况下，我尽我所能优化，并且规定：如果某一时刻起点的MINDIS值小于零，就退出。于是，不超时了。但是——

我始终无法接受居然两个节点之间不止一条边！！！！！！！！！！

——更令我无法接受的是，这创造了我编程史上的纪录：使用SPFA算法，没有一次直接成功的。用几次，错几次！

0

idontloveyj LV 3 @ 2007-09-05 19:40:14

但如果松弛了起点,也就是说本来dis=0,relax使dis

0

qword LV 8 @ 2007-09-05 18:45:45

编译通过...

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

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

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

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

├ 测试数据 05：答案正确... 9ms

├ 测试数据 06：答案正确... 9ms

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

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

Accepted 有效得分：100 有效耗时：18ms

两点之间有不只一条边！！！

WA死我啦！！！

0

subrays LV 5 @ 2007-07-09 15:20:10

编译通过...

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

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

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

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

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

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

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

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

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

0

mick LV 8 @ 2007-07-05 22:03:35

编译通过...

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

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

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

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

├ 测试数据 05：答案正确... 72ms

├ 测试数据 06：答案正确... 197ms

├ 测试数据 07：答案正确... 41ms

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

Accepted 有效得分：100 有效耗时：310ms

加上马甲共提交了36次包括此号的14次..!!

原因出在两点:

负权环与s不连接..(我将s与所有点都作1条虚线,原本相连的不用).

出现2点之间有x(x>=1)条线..(取权最小的1条)