首页 > 试题广场 >

图中每个圆圈是一个补给站，根据条件到B点后最多剩余的汽油量是

[单选题]
图中每个圆圈是一个补给站，存储着一定数量的汽油（在圈中标识），每个圈之间的路上标识了这段路需要消耗的汽油量，一辆小车从A点出发，在图上随意行走，到达某个补给站后，可以获得这个补给站的所有汽油，则其到B点后最多剩余的汽油量是____。 

  • 5
  • 6
  • 7
  • 9
  • 10
  • 13
查看正确选项
添加回答
我的天鸭头像 我的天鸭
AOE+动态规划

发表于 2019-06-04 10:40:54 回复(0)
pengxiang707头像 pengxiang707
E 可以使用A*算法获得
编辑于 2015-07-01 17:01:20 回复(0)
MTF-飞头像 MTF-飞
E
7-4-5-4-3-7-0
发表于 2015-06-16 16:45:55 回复(0)
牛牛12315头像 牛牛12315
这题目不严谨  因为存在回路  我可以不停地在回路里面跑   跑到加油 加到无穷大  再去B点  呵呵
所以要加个条件 —— 不走环路
发表于 2015-10-03 09:55:56 回复(11)
牛客384747号头像 牛客384747号
I think we can use AOE to solve such kind of question:
Build a directed graph basing on the original graph.The weight of it is the petrol supplied by destination vertex minus the weight of the former edge.
    
发表于 2016-01-10 17:14:32 回复(9)
繁星的夜空2012头像 繁星的夜空2012
这道题考察的就是最小生成树的问题。首先我们可以先找到该图的最小生成树。
如下图所示，

从A点出发，  油的数量为7， 消耗3  ，剩下4，到达补给站4
补给站4加油4， 油的数量是8，消耗2，剩下6，到达补给站5
补给站5加油5， 油的数量是11，消耗3，剩下8，到达补给站4
补给站4加油4，油的数量是12，消耗3，剩下9，大到补给站3
补给站3加油3，油的数量是12，消耗2，剩下10，到达补给站7
补给站7加油7，油的数量是17，消耗7，剩下10，到达补给站0，即终点B
故结果剩下就是10

发表于 2017-01-08 15:17:39 回复(8)
SunburstRun头像 SunburstRun
答案是E
这其实可以整理成一个有向带权图，图片上传不了
我口述一下，A 7->4->5->4->3->7->0 B
总共是 7+1+3+1+0+5-7=10
发表于 2015-06-16 22:48:22 回复(6)
ヤ我是一只好蛋头像 ヤ我是一只好蛋
先把图简化，圆圈里的数字减去他之前的路径权值，再赋给路径，然后求解就行了
7->4->5->4->3->7->0 
发表于 2019-09-28 10:02:04 回复(0)
恶寒轻轻头像 恶寒轻轻
试过转成有向图然后求关键路径，但存在环无法套用固定做法，但比起直接算会更容易看出答案。图中只有单向的情况是因为不可能有返回去的情况，同理有双向箭头的路是两个方向均可能才画出。如果用传统求最短路径方法，求ve，vl时就无法确定v2和v3的值，所以只是通过改有向图便于快速做题了。

编辑于 2021-11-24 16:47:58 回复(0)
JessciaChow头像 JessciaChow
类似求关键路径（Critical Path），只不过把AOE-网上活动的权值变成了负数，顶点也有了权值。不过由于是无向的，没有先后之分，应该每一步都选择能够使汽油剩余最大值的路线（结点-弧）即7-3+4-2+5-3+4-3+3-2+7-7 = 10
发表于 2016-09-28 15:08:18 回复(1)
小六神通头像 小六神通
利用地杰斯特拉算法，把地杰斯特拉算法中每次求最短路径的判断条件改为每次求耗油量最少，算出来就是最终结果
发表于 2017-03-07 10:41:05 回复(1)
ddssddgg头像 ddssddgg
这题如果是编程题的话就不能用迪杰斯特拉了吧，有负权回路了
发表于 2022-04-25 20:42:55 回复(0)
牛客508504998号头像 牛客508504998号
个人意见，先把该图化简，化简为只剩路径，而该路径的值为剩余的汽油，即前一个点所拥有的汽油数目减去该路程花费的汽油，那么该路径就只为剩余的汽油数（可正可负），然后再用AOE网络，求出B发生的最早时间即可
发表于 2020-02-29 21:45:25 回复(0)
Mr.DoubleU头像 Mr.DoubleU
感觉还是DFS画状态树来得快，老老实实画一个状态树吧，AOE网那个有回路吧，用那个英文回复的图画个状态树比较好
编辑于 2018-05-09 23:54:01 回复(0)
渣小白头像 渣小白
7+5+4+4+3+7-3-2-3-3-2-7=10
发表于 2017-08-06 23:33:52 回复(0)
程序猿爱攻城狮头像 程序猿爱攻城狮
不是最小生成树 也不是关键路径 依据题意要挨个的查
发表于 2018-04-02 08:22:40 回复(0)
想居家的小熊猫拥抱太阳头像 想居家的小熊猫拥抱太阳
最简单的方法。。用顶点的值减去边的权值，就是走那条边所获得的石油，最后挑一条加起来最大的路径，就是最省油的路线
发表于 2023-04-01 20:20:09 回复(0)
shikis1头像 shikis1
我直接暴力模拟
发表于 2023-01-23 10:10:30 回复(0)
熬夜的小山竹要发财头像 熬夜的小山竹要发财
就是求最小树，用贪心的那两个方法
发表于 2022-10-28 14:22:52 回复(0)
学术废物头像 学术废物
图上标记走这段路会导致油量有怎样的变化
发表于 2022-03-18 16:26:28 回复(0)
提交观点

问题信息

图
上传者：陈木木
难度：
39条回答 10594浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号