問題一覧 > 通常問題

No.1316 Maximum Minimum Spanning Tree

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 5
作問者 : optopt / テスター : tatyamtatyam 👑 hitonanodehitonanode
4 ProblemId : 5410 / 出題時の順位表
問題文最終更新日: 2020-12-14 14:15:46

これは,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もしくは右上の雲マークをクリックしてアカウントを作成してください。