LCP 16. Amusement park tour plan
subject
When it comes to the annual spring outing, Xiao Wu plans to visit the amusement park for one day. There are N amusement projects in the amusement park, numbered from 0 to N-1. Xiao Wu defines a non negative integer value[i] for each amusement project to represent his favorite value. There will be two-way paths between the two amusement projects. The whole amusement park has a total of M two-way paths, which are saved in the two-dimensional array edges. Xiao Wu plans to choose an amusement project a as the key project of this day. In the morning, Xiao Wu is going to play key project a and two projects B and C adjacent to project a (projects a, B and C require different projects, and project B and C require adjacent projects), and return to a, that is, there is a path of A-B-C-A. In the afternoon, Xiao Wu decided to visit key project a and two adjacent projects B 'and C' (projects a, B 'and C' require different projects, and project B 'is adjacent to project C') and return to a, that is, there is a path of A-B '- C' - a. Afternoon play items B 'and C' can have duplicate items with morning play items B and C. Xiao Wu hopes to arrange the travel path in advance to maximize the sum of his favorite values. Please return the sum of the maximum favorite values that meet the selection conditions of the play path. If there is no such path, return 0. Note: playing the same item repeatedly in a day can't increase your favorite value repeatedly. For example, if the travel paths in the morning and afternoon are A-B-C-A and A-C-D-A respectively, you can only get the sum of value[A] + value[B] + value[C] + value[D].
Example 1:
Input: edges = [[0,1],[1,2],[0,2]], value = [1,2,3]
Output: 6
Explanation: one of the schemes with the highest sum of favorite values is 0 - > 1 - > 2 - > 0 and 0 - > 2 - > 1 - > 0. Playing the same point repeatedly will not be counted into the favorite value, and 1 + 2 + 3 = 6 will be returned
Example 2:
Input: edges = [[0,2],[2,1]], value = [1,2,5]
Output: 0
Explanation: if there is no playing path that meets the requirements, return 0
Example 3:
Input: edges = [[0,1],[0,2],[0,3],[0,4],[0,5],[1,3],[2,4],[2,5],[3,4],[3,5],[4,5]], value = [7,8,6,8,9,7]
Output: 39
Explanation: one of the schemes with the highest sum of favorite values is 3 - > 0 - > 1 - > 3 and 3 - > 4 - > 5 - > 3. The highest favorite value is 7 + 8 + 8 + 9 + 7 = 39
Restrictions: 3 <= value.length <= 10000 1 <= edges.length <= 10000 0 <= edges[i][0],edges[i][1] < value.length 0 <= value[i] <= 10000 edges There are no duplicate edges in the edges[i][0] != edges[i][1]
Folk solution
- thinking
1. Problem transformation, which transforms the problem of this kind of graph into the problem of tree
2. First save the points that can be reached by each point with a linked list
3. The next step is traversal. First traverse the first point, and then traverse the second point according to the first point
4. The choice of the morning will affect the choice of the afternoon. All need to deal with the morning and afternoon together
5. Finally, the maximum value is returned in the results of each enumeration
- answer
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* When it comes to the annual spring outing, Xiao Wu plans to visit the amusement park for one day. There are N amusement projects in the amusement park, numbered from 0 to N-1.
* Xiao Wu defines a non negative integer value[i] for each amusement project to represent his favorite value.
* There will be two-way paths between the two amusement projects. The whole amusement park has a total of M two-way paths, which are saved in the two-dimensional array edges.
* Xiao Wu plans to choose an amusement project A as the key project of this day.
* In the morning, Xiao Wu is going to play key project A and two projects B and C adjacent to project A (projects A, B and C require different projects, and project B and C require adjacent projects), and return to A, that is, there is A path of A-B-C-A.
* In the afternoon, Xiao Wu decided to visit key project a and two adjacent projects B 'and C' (projects a, B 'and C' require different projects, and project B 'is adjacent to project C') and return to a, that is, there is a path of A-B'-C'-A.
* Afternoon play items B 'and C' can have duplicate items with morning play items B and C.
* Xiao Wu hopes to arrange the travel path in advance to maximize the sum of his favorite values.
* Please return the sum of the maximum favorite values that meet the selection conditions of the play path. If there is no such path, return 0.
* Note: playing the same item repeatedly in a day can't increase your favorite value repeatedly.
* For example, if the travel paths in the morning and afternoon are A-B-C-A and A-C-D-A respectively, you can only get the sum of value[A] + value[B] + value[C] + value[D].
*
*/
public class Solution16 {
public int maxWeight(int[][] edges, int[] value) {
if (null == edges || edges.length < 3) {
return 0;
}
Map<Integer, List<Integer>> map = new HashMap<>();
for (int[] edge : edges) {
List<Integer> list = map.get(edge[0]);
if (null == list) {
list = new ArrayList<>();
map.put(edge[0], list);
}
list.add(edge[1]);
list = map.get(edge[1]);
if (null == list) {
list = new ArrayList<>();
map.put(edge[1], list);
}
list.add(edge[0]);
}
return getMax(map, value);
}
public int getMax(Map<Integer, List<Integer>> map, int[] value) {
int maxCount = 0;
for (int a : map.keySet()) {
for (int b : map.get(a)) {
for (int c : map.get(b)) {
if (c == a) {
continue;
}
for (int d : map.get(c)) {
if (a == d) {
for (int e : map.get(a)) {
for (int f : map.get(e)) {
if (f == a) {
continue;
}
for (int g : map.get(f)) {
if (g == a) {
int count = value[a] + value[b] + value[c] + value[e] + value[f];
if (e == b || e == c) {
count -= value[e];
}
if (f == b || f == c) {
count -= value[f];
}
if (count > maxCount) {
maxCount = count;
}
}
}
}
}
}
}
}
}
}
return maxCount;
}
}
- Sorry, it's a little scary ~
- There was no accident. Indeed, it timed out
- When considering how to use dynamic programming or add memory array for this problem