Рассмотрим топологическую сортировку вашего DAG.
Для списка L, соответствующего топосорту вашего графа, у вас есть в конце листья. Тогда для вершины непосредственно перед
L = [..., v, leaves]
вы знаете, что ребра, выходящие из v, могут только go к вершинам после (здесь leaves). Это позволяет вам вычислить минимальный вес, связанный с v, применяя максимум Дамьена
Делайте это до головы L.
Топологическая сортировка O (V + E)
Вот иллюстрация с более интересным графиком (прочитайте его сверху вниз)
5
/ \
4 7
1 2
0
6
Порядок топологии: (4601275)
Таким образом, мы посетим в порядке 4,6,0,1,2,7, затем 5, и у каждой вершины, которую мы посетим, все ее зависимости уже вычислены.
Предположим, что у каждой вершины k есть событие, происходящее после 2^k дней. Следующая дата называется весом.
например, вершина 4 взвешена 2^4
Предположим, что каждое ребро (i,j) взвешено 5*i + j
- 6 взвешивается
2^6 = 64 - 0 взвешивается
max(2^0, 64 + (0*5+6)) = 70 - 1 занимает
max(2^1, 70 + 5) = 75 - 7 принимает
max(2^7, 75 + 5*7+1, 2^2) = 2^7
Балл Следует отметить (здесь для 7), что минимальная дата, вызванная зависимостями узла, может произойти до даты, прикрепленной к этому узлу. (и мы должны сохранить самый большой)
function topologicalSort({ V, E }) {
const visited = new Set ()
const stack = []
function dfs (v) {
if (visited.has(v)) { return }
E.has(v) && E.get(v).forEach(({ to, w }) => dfs(to))
visited.add(v)
stack.push(v)
}
// process nodes without incoming edges first
const heads = new Set ([...V])
for (const v of V) {
const edges = E.get(v)
edges && edges.forEach(({ to }) => heads.delete(to))
}
for (const v of heads) {
dfs(v)
}
for (const v of V) {
dfs(v)
}
return stack
}
class G {
constructor () {
this.V = new Set()
this.E = new Map()
}
setEdges (from, tos) {
this.V.add(from)
tos.forEach(({ to, w }) => this.V.add(to))
this.E.set(from, tos)
}
}
function solve ({ g, vToWeight }) {
const stack = topologicalSort(g)
console.log('ordering', stack.join(''))
stack.forEach(v => {
const edges = g.E.get(v)
if (!edges) { return }
const newval = Math.max(
vToWeight.get(v),
...edges.map(({ to, w }) => vToWeight.get(to) + w)
)
console.log('setting best for', v, edges.map(({ to, w }) => [vToWeight.get(to), w].join('+') ))
vToWeight.set(v, newval)
})
return vToWeight
}
function demo () {
const g = new G ()
g.setEdges(2, [{ to: 1, w: 5 }])
g.setEdges(4, [{ to: 2, w: 2 }, { to: 3, w: 4 }])
const vToWeight = new Map ([
[1, 1],
[2, 6],
[3, 3],
[4, 4]
])
return { g, vToWeight }
}
function demo2 () {
const g = new G ()
const addEdges = (i, ...tos) => {
g.setEdges(i, tos.map(to => ({ to, w: 5 * i + to })))
}
addEdges(5,4,7)
addEdges(7,1,2)
addEdges(1,0)
addEdges(0,6)
const vToWeight = new Map ([...g.V].map(v => [v, 2**v]))
return { g, vToWeight }
}
function dump (map) {
return [...map].map(([k, v])=> k+'->'+v)
}
console.log('----op\s sol----\n',dump(solve(demo())))
console.log('----that case---\n',dump(solve(demo2())))