第一问答网»论坛 › 中问网 › 问答 › SPFA怎么使用拓扑排序预处理负权值回路啊？ ...

SPFA怎么使用拓扑排序预处理负权值回路啊？

11 |

1 | 2012-4-20 15:39:53 | 显示全部楼层 |阅读模式

一般的问题spfa是不需要判断负权回路的，因为一旦出现了负权回路相当于给问题无解。(因为求的是最短路，要是有负权回路的话，就可以已知在那个负权回路里绕圈)，因此这“不是讨论的重点”重点是求出最短路！做题的时候可以先不考虑无解……如果一定要判断无解的话，那么……考试的话它也就值10分，建议你还是我要去判断了。这“不是讨论的重点”。至今为止我还没有遇上出现负权回路的问题。最多也就有负权边，一般是不会出现负权值回路的。即使在用spfa做最小费用最大流的时候，负权值回路都不存在。只要你相信最短路一定存在，那么就不需要管这些了。另外，不是“有负权值回路运行SPFA复杂度就太高了”而是“有负权值回路运行SPFA就会死循环”。还有...

使用道具举报

返回列表发新帖

千问

主题	0 回帖	4882万积分

论坛元老

Rank: 8 Rank: 8

积分: 48824836

回复楼主返回列表

问答

热门排行