問題一覧 > 通常問題

No.1316 Maximum Minimum Spanning Tree

レベル : / AI推定難易度 : 2925 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 12
作問者 : opt / テスター : tatyam 👑 hitonanode
お気に入りにしたユーザー ProblemId : 5410 / 自分の提出
問題文最終更新日: 2021-02-17 21:10:21
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2020 (順位表) の他の問題:

This is the problem for day 13 of Advent Calendar Contest 2020.

Problem Statement

There is a simple connected undirected graph $G$ with $N$ vertices and $M$ edges. The vertices are numbered $1,\dots,N$ and the edges are numbered $1,\dots,M$, and edge $i$ $(1 \leq i \leq M)$ connects vertices $a_i, b_i$. In addition, positive integers $c_i, d_i$ are defined for edge $i$.

You are given a positive integer $K$. When you choose a real value $x_i$ greater than or equal to $0$ for each edge $i$, the score is determined accordingly by the following expression:
$K \times \Big($the total weight of a minimum spanning tree of graph $G$ when the weight of edge $i$ is $(c_i + x_i)$$\Big) - \displaystyle \sum_{i=1}^M d_i x_i.$

Determine whether the score has a maximum value, and if it does, find the maximum value. It can be proved that the maximum value (if it exists) is an integer, so output it as an integer.

Constraints

  • All input values are integers
  • The given graph is simple (contains no multiple edges or loops) and connected
  • $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)$

Input

The input is given from standard input in the following format: 

$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$

Output

If the score has a maximum value, output the maximum value as an integer. If it does not, output -1. Finally, output a newline.

Sample

Sample 1
Input
3 3 10
1 2 4 9
1 3 5 8
2 3 6 7
Output
94

For example, if $(x_1, x_2, x_3) = (2, 1, 0)$, then $(c_1+x_1, c_2+x_2, c_3+x_3) = (6, 6, 6)$, and the total weight of a minimum spanning tree of $G$ is $12$. The score in this case is $10 \times 12 - (9 \times 2 + 8 \times 1 + 7 \times 0) = 94$.

The score cannot be made greater than $94$, so output $94$.

Sample 2
Input
3 3 10
1 2 9 4
1 3 8 5
2 3 7 6
Output
-1

For example, if $(x_1, x_2, x_3) = (10^{100}, 10^{100}, 10^{100})$, the score is $5 \times 10^{100} + 150$.

In this way, the score can be made arbitrarily large, and no maximum value exists. Therefore, output -1.

Sample 3
Input
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
Output
67
Sample 4
Input
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
Output
24370210367515244

Beware of overflow.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。