1948. 임계경로

1948번: 임계경로

---

문제가 조금 난해하게 쓰여 있지만, 사실 ``최장 경로`` 문제이다. 즉 최장 경로의 길이를 구하고, 최장 경로에 포함되는 간선의 수를 구하는 문제이다.

 

# 맞왜틀 1 (펼치기)

최장 경로가 여러 개 있을 경우, 각 경로가 포함하는 간선을 모두 세어야 한다. 예를 들어 다음과 같은 경우가 있다.

# 입력
4 6
1 2 1
2 3 2
1 3 3
1 3 3
1 4 2
4 3 1
1 3

# 출력
3
6

 

일반적인 그래프에서의 최장 경로 문제는 ``NP-complete``이다. 하지만 이 문제에서는 그래프가 유향이므로 전형적인 재귀 DP를 이용하여 문제를 해결할 수 있다. $d[i]$를 $i$번 정점에서 도착 정점까지의 최장 경로의 길이라고 할 때, $i$번 정점과 연결된 모든 정점 $j$에 대해 $d[i]=\max(d[j]+cost[i][j])$이다. 

 

그런데 문제에서 추가로 간선의 개수까지 요구하고 있고, ``맞왜틀 1`` 때문에 어떤 식으로든 최장 경로를 추적할 필요가 있다. 나는 최장 경로에서 $i$번 정점 이후의 정점을 $track[i]$에 저장하고, 나중에 따로 BFS하는 방법으로 간선을 셌다.

 

# 맞왜틀 2 (펼치기)

``맞왜틀 1``의 입력처럼 같은 간선이 여러 개 주어질 수도 있고, 하필 그러한 간선이 최장 경로에 포함될 수도 있다. 이럴 때 일반적인 BFS로는 정답을 구할 수 없다.

 

큐에 넣는 양식(방문 처리 등)은 그대로 하되, 큐에서 꺼내는 모든 정점 $cur$에 대해 $track[cur]$의 크기의 합을 반환해야 한다.

---

플레5 치곤 쉬운 문제.