가성비 유량

야요이는 절약의 달인이다. 값이 싸다는 이유만으로 물건을 고르지는 않고, 늘 "가성비"를 따진다. 콩나물 요리에 능한 것도 그 때문이다. 절약 실력이 알려지면서 야요이에게는 온갖 비용을 줄여 달라는 부탁이 들어온다. 이번 일감은 네트워크 유량 최적화다.

방향 그래프 $G = (V, E)$를 생각하자. $V = \{1, 2, \dots, |V|\}$는 정점 집합이고, $E \subset V \times V$는 간선 집합이다. 각 간선 $e$에는 용량 $u(e)$와 비용 $c(e)$가 붙어 있다. 두 정점 $s$와 $t$에 대해 함수 $f_{s,t} : E \to \mathbb{R}$가 다음 두 조건을 만족하면 $s$-$t$ 유량이라고 부른다.

• 모든 간선 $e \in E$에서 $0 \le f_{s,t}(e) \le u(e)$이다.
• $s$와 $t$를 제외한 모든 정점 $v \in V \setminus \{s, t\}$에서 들어오는 유량의 합과 나가는 유량의 합이 같다. 즉 $\sum_{e = (w, v) \in E} f_{s,t}(e) = \sum_{e = (v, w) \in E} f_{s,t}(e)$이다.

$f_{s,t}$의 유량값과 비용은 각각 다음과 같이 정의한다.

$F(f_{s,t}) = \sum_{e = (s, v) \in E} f_{s,t}(e) - \sum_{e = (v, s) \in E} f_{s,t}(e), \qquad C(f_{s,t}) = \sum_{e \in E} f_{s,t}(e) c(e)$

네트워크 유량 최적화는 보통 최대 유량을 흘리면서 비용을 최소로 만드는 문제를 뜻한다. 야요이의 기준은 가성비다. 모든 $s$-$t$ 유량 $f$에 대한 최대 유량값을 $F_{\max} = \max_f F(f)$라 하고, $s$-$t$ 유량 $f_{s,t}$의 균형 함수를 다음과 같이 정의한다.

$B(f_{s,t}) = C(f_{s,t})^2 + (F_{\max} - F(f_{s,t}))^2$

야요이는 $B$를 최소로 만드는 유량이 가성비가 가장 좋다고 본다. 모든 $s$-$t$ 유량에 대한 $B(f_{s,t})$의 최솟값을 구하라.

입력은 테스트 케이스 하나로 이루어진다. 첫 줄에 정점의 개수 $N$ ($2 \le N \le 100$)과 간선의 개수 $M$ ($1 \le M \le 1\,000$)이 공백 하나로 구분되어 주어진다. 둘째 줄에 두 정점 $s$와 $t$ ($1 \le s, t \le N$, $s \ne t$)가 주어진다. 이어지는 $M$개의 줄 중 $i$번째 줄에는 네 정수 $a_i$, $b_i$, $u_i$, $c_i$가 주어진다. $i$번째 간선은 $a_i$에서 $b_i$로 향하고 ($1 \le a_i, b_i \le N$), 용량은 $u_i$ ($1 \le u_i \le 100$), 비용은 $c_i$ ($1 \le c_i \le 100$)이다. 모든 $i$에서 $a_i \ne b_i$이고, $i \ne j$이면 $(a_i, b_i) \ne (a_j, b_j)$이다.

$B$의 최솟값을 기약분수로 한 줄에 출력한다. 정확히는 "u/d" 형식으로 출력하며, $u$는 분자, $d$는 분모다. $u$와 $d$는 음이 아닌 정수이고 최대공약수가 1이어야 한다. 답은 항상 유리수다. 최솟값이 0이면 "0/1"을 출력한다.