연쇄 반응 timer 5s memory 1024MB

와일리(Wile)는 사막에서 혼자 살기 때문에, 연쇄 반응(chain reaction)으로 작동하는 복잡한 기계를 만들며 스스로를 즐겁게 한다. 각 기계는 \mathbf{N}개의 모듈로 이루어져 있고, 각 모듈은 1, 2, \dots, \mathbf{N}으로 번호가 매겨져 있다. 각 모듈은 자신보다 번호가 작은 다른 모듈 하나를 가리킬 수도 있다. 그렇지 않다면 심연(the abyss)을 가리킨다.

어떤 모듈도 자신을 가리키지 않을 때, 그 모듈을 시동 모듈(initiator)이라고 한다. 와일리는 시동 모듈을 손으로 직접 작동시킬 수 있다. 모듈 하나가 작동되면, 그 모듈이 가리키는 모듈(있다면)을 작동시키고, 그 모듈이 또 다른 모듈을 가리키면 그것도 작동시키는 식으로 연쇄적으로 진행된다. 이 과정은 연쇄가 심연에 도달하거나, 이미 작동된 모듈에 도달하려는 순간에 멈춘다. 이것을 연쇄 반응(chain reaction)이라고 한다.

\mathbf{N}개의 각 모듈에는 재미 지수(fun factor) \mathbf{F_i}가 있다. 연쇄 반응 하나에서 와일리가 얻는 재미는, 그 연쇄 반응에서 작동된 모든 모듈의 재미 지수 중 최댓값이다. 와일리는 모든 시동 모듈을 각각 한 번씩, 어떤 순서로든 손으로 작동시킬 것이다. 전체 세션에서 와일리가 얻는 총 재미는 각 연쇄 반응에서 얻는 재미를 모두 더한 값이다.

예를 들어 모듈이 4개이고 재미 지수가 \mathbf{F_1}=60, \mathbf{F_2}=20, \mathbf{F_3}=40, \mathbf{F_4}=50라고 하자. 또한 모듈 1은 심연을 가리키고, 모듈 2와 3은 모듈 1을 가리키며, 모듈 4는 모듈 2를 가리킨다고 하자. 이때 시동 모듈은 3과 4 두 개이며, 와일리는 이 둘을 어떤 순서로든 작동시켜야 한다.

위에서 보듯, 만약 와일리가 모듈 4를 먼저 작동시키면 모듈 4, 2, 1이 같은 연쇄 반응에서 작동되고, 이때 얻는 재미는 \max(50, 20, 60) = 60이다. 그 다음 와일리가 모듈 3을 작동시키면, 모듈 3만 단독으로 작동된다(모듈 1은 다시 작동될 수 없다). 이때 얻는 재미는 40이므로, 세션의 총 재미는 60+40=100이다.

하지만 와일리가 모듈 3을 먼저 작동시키면, 모듈 3과 1이 같은 연쇄 반응에서 작동되어 얻는 재미는 \max(40, 60) = 60이다. 그 다음 와일리가 모듈 4를 작동시키면, 모듈 4와 2가 같은 연쇄 반응에서 작동되어 얻는 재미는 \max(50, 20) = 50이고, 세션의 총 재미는 60+50=110이다.

모듈들의 재미 지수와 연결 구조가 주어질 때, 시동 모듈들을 최적의 순서로 손으로 작동시켜 얻을 수 있는 총 재미의 최댓값을 구하라.