Дано: невзвешенный неориентированный граф (циклический) G (V, E), каждая вершина имеет два заданных значения (скажем, A и B), и никакие две смежные вершины не имеют одинаковое значение A.Найдите простой путь, имеющий максимальную сумму значений B вершин, со следующими ограничениями:1) Этот путь содержит вершины с одинаковыми значениями A, или он может иметь не более двух разных значений A (эти значения должны быть чередующимися, поскольку никакие две соседние вершины не могут иметь одинаковое значение A)
рис
На рис.Самый длинный простой путь начинается с вершины 2 и заканчивается в 5, все вершины имеют не более 2 различных значений 1 и 2, также они поочередно находятся в пути 1,2,1,2,1 и выводят суммы значений B.Помните: вершина 6 может быть ответом, если значение B 6 равно 13, потому что сумма пути решения равна 12.
int dfs(int source, int parent, int score){
for each vertex V(V!=p) connected to source:
if(!vis[V]{
if(A[parent]==A[V]){
recur : dfs(V,source,B[source]+score)
}
}
return score+B[source];
}
Это дает неправильный answer.no.вершин <= 1000000 </p>