#1187. 有理数

现有有向图$(V,E)$，$|V|=n,|E|=m$。 一条边的流量上限为 $cap(e)$ ，边的单位流量费用是 $cost(e)$。源点、汇点分别是 $s,t$。

一个流 $f$ "合法"，当且仅当对于每条边 e，$0 \le f(e) \le cap(e)$，且除源汇两点外每个点的流入流量等于流出流量。

定义流 $f$ 的流量 $F(f)$ 和费用 $C(f)$ 分别为:

• $F(f)$ 等于源点的流出流量减流入流量

• $C(f)$ 等于每条边的流量乘以单位费用的和，即 $Σf(e)*cost(e)$。

现在定义一个函数 $G(f)=C(f)^2 +(MaxFlow-F(f))^2$ ，其中 MaxFlow 等于 $\max\{F(f)\}$，最大流的流量。

要求求出一个合法的流 $f$，使得 $G(f)$ 最小，以最简分数 p/q 的形式输出最小的 $G(f)$，保证答案为有理数。

第一行两个正整数 $n,m$。 第二行两个正整数 $s,t$ 表示源点和汇点。 接下来 $m$ 行，每行四个正整数 $u,v,cap,cost$，表示有一条 $u$ 到 $v$ 的容量上界为 $cap$，单位费用为 $cost$ 的边。

一行一个分数 p/q 表示最小的 $G(f)$。

$n,u,c≤100,m≤1000$。