問題一覧 > 通常問題

No.2642 Don't cut line!

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 51
作問者 : abap34abap34 / テスター : noya2noya2 ponjuiceponjuice
4 ProblemId : 10681 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-02-19 21:28:31

問題文

$N$ 頂点 $K$ 辺の連結な単純無向グラフ $G = (V, E)$ があります。
それぞれの頂点には $1$ から $N$ までの番号が、辺には $1$ から $K$ までの番号がついていて、 $i$ 番の辺は番号が $u_i$ と $v_i$ の頂点を結んでおり、コスト $w_i$ と利益 $p_i$ が定まっています。
$G$ の全域木 $T$ に対して、その辺の番号の集合を $I$ として、次のように $T$ のコスト $W(T)$ と利益 $P(T)$ を定義します。

  • $\displaystyle W(T) = \sum_{i \in I} w_i$
  • $\displaystyle P(T) = \max_{i \in I}\ p_i$
すなわち、全域木のコストは辺のコストの総和、利益は辺の利益の最大値です。
ここで、全域木の許容コスト $C$ が与えられます。
$W(T) \leq C$ を満たすような $T$ について、 $P(T)$ の最大値を求めて出力してください。
そのような $T$ が存在しない場合は、 $-1$ を出力してください。

入力

$N \ K \ C$
$u_1 \ v_1 \ w_1 \ p_1$
$u_2 \ v_2 \ w_2 \ p_2$
$\vdots$
$u_K \ v_K \ w_K \ p_K$

  • $1 \leq N \leq 10^5$
  • $1 \leq K \leq 10^5$
  • $1 \leq C \leq 10^{10}$
  • $1 \leq w_i, p_i \leq 10^{5}$ $(i = 1, 2, \cdots, K)$
  • 与えられるグラフは連結な単純無向グラフ
  • 入力はすべて整数

出力

条件を満たす $T$ について、$P(T)$ の最大値を出力してください。 条件を満たす $T$ が存在しない場合は $-1$ を出力してください。

サンプル

サンプル1
入力
3 3 1000
1 2 20 20
2 3 10 10
3 1 1 1
出力
20

入力は以下のようなグラフになります。



このグラフに対しては、下図の赤い辺からなる全域木 $T$ を考えると、これはコストの条件 $W(T) = 20 + 10 \leq 1000$ を満たしていて、
$P(T) = 20$ となり、最大値となります。


サンプル2
入力
5 7 10
1 2 3 4
1 3 2 4
2 3 10 20
3 4 1 3
2 4 2 2
2 5 4 2
4 5 3 3
出力
4
サンプル3
入力
3 3 1
1 2 100 100
2 3 100 100
3 1 100 100
出力
-1

このグラフのどんな全域木 $T$ も $W(T) \leq C$ を満たしません。

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