Editorial

---

E

문제 요약: DAG가 있는데 정확히 하나의 노드에만 out edge가 없다.

1초에 한 번씩, 다음 operation이 실행된다.

Let S be the set of nodes x that have ax>0.

For all x∈S, 1 is subtracted from ax, and then for each node y, such that there is an edge from x to y, 1 is added to ay.

몇초만에 모든 노드의 수가 0이 되는지 구하는 문제이다.

문제 해설:

먼저 out edge가 없는 노드를 sink point 라고 하자.

모든 노드에 대해

$d_i = $ 노드 $i$에 1이 있었을 때 최종적으로 sink point에 추가되는 1의 개수

$sum_i = $ 노드 $i$에 있는 수

라고 정의하면,

먼저 중간에 비는 노드($a_i=0$인 노드) 를 제거해서 sink point 에서 1초에 1씩 빠져나가게 하기 위해 n초를 시뮬레이션한다.

전체 수의 총량이 1초에 sink point에서 1씩 빠져나가게 되므로,

답은 시뮬레이션 한 $n$과 노드에서 sink point로 가게 되는 개수와 그 노드가 가지고 있던 수만큼 sink point로 가게 되므로 가지고 있던 수 $a_i$를 곱해서 모두 더한 값이다.

즉, 처음 시뮬레이션 했던 n초를 더해 \(ans=n+\displaystyle \sum_{i \in S} {d_i * sum_i}\) 가 된다.

의견:

sink point 에서 1초에 1씩 항상 빠져나가게 해야 \(ans = n+\displaystyle \sum_{i \in S} {d_i * sum_i}\)이 되므로, n번을 시뮬레이션 하는 것이 중요한 것 같다.