No.1316 Maximum Minimum Spanning Tree
タグ : / 解いたユーザー数 8
作問者 :
opt
/ テスター :
tatyam
hitonanode
これは，Advent Calendar Contest 2020 の 13 日目の問題です．
問題文
$N$ 頂点 $M$ 辺からなる単純かつ連結な無向グラフ $G$ があります． 頂点には番号 $1,\dots,N$ が，辺には番号 $1,\dots,M$ がついており，辺 $i$ $(1 \leq i \leq M)$ は頂点 $a_i, b_i$ を繋いでいます． また，辺 $i$ には正の整数 $c_i, d_i$ が定まっています．
正の整数 $K$ が与えられます．
あなたが各辺 $i$ に対し $0$ 以上の実数値 $x_i$ を定めると，それに応じてスコアが以下の式で定まります:
$K \times \Big($グラフ $G$ において，辺 $i$ の重みを $(c_i + x_i)$ としたときの最小全域木の重み和$\Big) - \displaystyle \sum_{i=1}^M d_i x_i.$
スコアに最大値が存在するかを判定し，存在するならば最大値を求めてください． 最大値は（存在するならば）整数であることが証明できるので，整数で出力してください．
制約
- 入力はすべて整数
- 与えられるグラフは単純（多重辺とループを含まない）かつ連結
- $2 \leq N \leq 50$
- $N-1 \leq M \leq 200$
- $1 \leq K \leq 10^8$
- $1 \leq a_i, b_i \leq N \quad (1 \leq i \leq M)$
- $1 \leq c_i, d_i \leq 10^8 \quad (1 \leq i \leq M)$
入力
入力は以下の形式で標準入力から与えられる:
$N \hspace{0.8em} M \hspace{0.8em} K$
$a_1 \hspace{0.8em} b_1 \hspace{0.8em} c_1 \hspace{0.8em} d_1$
$a_2 \hspace{0.8em} b_2 \hspace{0.8em} c_2 \hspace{0.8em} d_2$
$\ \vdots$
$a_M \hspace{0.8em} b_M \hspace{0.8em} c_M \hspace{0.8em} d_M$
出力
スコアに最大値が存在するならば，最大値を整数で出力せよ．
存在しないならば，-1 を出力せよ．
最後に改行を出力すること．
サンプル
サンプル1
入力
3 3 10 1 2 4 9 1 3 5 8 2 3 6 7
出力
94
例えば $(x_1, x_2, x_3) = (2, 1, 0)$ とすると，$(c_1+x_1, c_2+x_2, c_3+x_3) = (6, 6, 6)$ となり，$G$ の最小全域木の重み和は $12$ となります． このときのスコアは $10 \times 12 - (9 \times 2 + 8 \times 1 + 7 \times 0) = 94$ です．
スコアを $94$ より大きくすることはできないため，$94$ を出力します．
サンプル2
入力
3 3 10 1 2 9 4 1 3 8 5 2 3 7 6
出力
-1
例えば $(x_1, x_2, x_3) = (10^{100}, 10^{100}, 10^{100})$ とすると，スコアは $5 \times 10^{100} + 150$ となります．
このようにスコアはどれだけでも大きくでき，最大値は存在しません．
そのため -1 を出力します．
サンプル3
入力
5 6 4 5 2 6 7 1 2 6 2 5 4 1 3 1 4 10 4 5 3 1 2 3 2 2 5
出力
67
サンプル4
入力
10 25 92211971 4 2 18944282 65759207 9 6 15962423 10621616 3 8 47914521 56141000 5 8 66635310 41377947 7 2 65108022 65066806 6 4 50098226 10814748 10 2 60782975 72616715 10 8 30925144 10882291 3 2 49106825 16363753 1 2 69961917 11421213 9 3 45817455 25601921 2 5 10896405 67692981 9 10 19849113 47342344 2 8 11714206 13670279 1 7 16090031 57815628 6 1 77406223 17253146 4 1 21226805 93997182 4 7 59045989 57241303 7 9 29546553 63757135 2 6 11490989 27602450 10 7 49565844 14810337 10 6 10224547 33412583 10 4 43949741 78660119 4 5 10490538 34344562 4 3 11086555 20386751
出力
24370210367515244
オーバーフローに注意してください．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。