그냥 하는 노트와 메모장

A에서 B로 갈 수 있는 모든 경로의 차의 수 최대값은 최대 유량으로 충분히 가능하다. 하지만 또 하나가 있는게 이 중에서도 한 경로만 사용했을 때, 최대값을 구해서 앞서 구한 모든 경로의 차의 최대값과 한 경로의 차의 수 최대값의 비율을 계산하라고 한다. 단순 최대유량 문제만 내기엔 부족했나보다. 편의상 A에서 B로 가는 모든 경로의 차의 수 최대값을 X라고 하고, 한 경로의 차의 수 최대값을 Y라고하면 구하고자 하는 값은 Y/X가 된다. X는 단순 최대 유량으로 구해서 계산하며 Y는 backtracking으로 정의하여 계산한다. Y를 구할 때, 기저 사례는 B를 만날 때까지고, 재귀를 돌며 방문했던 정점은 다시 방문하지 않도록 한다. 재귀의 반환값은 현재 정점에서 방문 가능한 정점 중에서 차를 최대한..