首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

[传递闭包+SPFA最长谈判正环]poj 1932:XYZZY

2012-09-20 
[传递闭包+SPFA最长路判正环]poj 1932:XYZZY大致题意:? ? 给出一个由n个房子,由若干的单向路连接起来,每个

[传递闭包+SPFA最长路判正环]poj 1932:XYZZY

大致题意:

? ? 给出一个由n个房子,由若干的单向路连接起来,每个房子都有一个权值,意味着进入这个房子得到或者消耗的能量。把你放在1点,给你100点的初始能量。现在问你能否到达n点且到达时权值大于0.

?

大致思路:
? ? 很好的题目,参考了小媛神的思路 Orz。首先用spfa求最长路,同时判定是否存在正圈,再用floyd求出传递闭包。如果spfa求出的dis[1,n]大于0。或者从起点可以到达某个正圈,且这个正圈可以到达终点,则认为存在可行方案。

?

? 

热点排行