Atlassian oa题， 做不来求帮助。。

帮同学问的，在地里找到的oa题。没有头绪，求大佬指点

搜一下吧，有人贴过答案，比较难理解的是u和v两个数据，意思是一个路径从u走到v，同一个index
比如
u = [2,4]
v = [1,0]
表示2条路径，从2<=>1和4<=>0，注意路径是双向的

1. require 'set'
   
2. 
   
3. def find_best_path(n, m, max_t, beauty, u, v, t)
   
4.   $max_beauty = 0
   
5. 
   
6.   paths = {}
   
7.   times = {}
   
8.   u.each_with_index do |from, i|
   
9.     current = v[i]
   
10.     times[i+1] = t[i]
    
11. 
    
12.     if paths.key? from
    
13.       paths[from] << current
    
14.     else
    
15.       paths[from] = [current]
    
16.     end
    
17. 
    
18.     if paths.key? current
    
19.       paths[current] << from
    
20.     else
    
21.       paths[current] = [from]
    
22.     end
    
23.   end
    
24. 
    
25.   dfs(paths, {0 => 1}, [].to_set, 0, beauty[0], max_t, times, beauty)
    
26.   $max_beauty
    
27. end
    
28. 
    
29. def dfs(paths, visited_cities, visited_paths, city, current_beauties, time_left, times, beauties)
    
30.   if time_left < 0
    
31.     return
    
32.   end
    
33. 
    
34.   if city == 0
    
35.     $max_beauty = [$max_beauty, current_beauties].max
    
36.   end
    
37. 
    
38.   paths[city].each do |next_city|
    
39.     path = "#{city}|#{next_city}"
    
40.    
    
41.     if visited_paths.include?(path)
    
42.       next
    
43.     else
    
44.       visited_paths << path
    
45.     end
    
46. 
    
47.     city_beauties = current_beauties
    
48.     if visited_cities.key?(next_city)
    
49.       visited_cities[next_city] += 1
    
50.     else
    
51.       visited_cities[next_city] = 1
    
52.       city_beauties += beauties[next_city]  
    
53.     end
    
54. 
    
55.     spend_time = times[[city, next_city].max]
    
56. 
    
57.     dfs(paths, visited_cities, visited_paths, next_city, city_beauties, time_left - spend_time, times, beauties)
    
58.     visited_paths.delete(path)
    
59.     visited_cities[next_city] -= 1
    
60.     if visited_cities[next_city] == 0
    
61.       visited_cities.delete(next_city)
    
62.     end
    
63.   end
    
64. end
    
65. 
    
66. u = [0,1,0]
    
67. v = [1,2,3]
    
68. t = [6,7,10]
    
69. beauty = [5,10,15,20]
    
70. 
    
71. p find_best_path(4, 3, 30, beauty, u, v, t) #30
    
72. 
    
73. 
    
74. u = [0,2,0]
    
75. v = [1,0,3]
    
76. t = [10,13,17]
    
77. beauty = [0,32,10,43]
    
78. 
    
79. p find_best_path(4, 3, 49, beauty, u, v, t) #43
    

复制代码

这题有说是树，DAG或者是图吗？如果是树（猜的），那么还有个combinational sum的问题。比如时间充裕，我回到旅馆后还可以再选择一条线路。

14417335 发表于 2019-4-6 03:52
这题有说是树，DAG或者是图吗？如果是树（猜的），那么还有个combinational sum的问题。比如时间充裕，我回 ...

更像无向图吧，你说的办法的确可以