問題一覧 > 通常問題

No.2642 Don't cut line!

レベル : / AI推定難易度 : 1725 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 52
作問者 : abap34 / テスター : noya2 ponjuice
お気に入りにしたユーザー ProblemId : 10681 / 自分の提出
問題文最終更新日: 2024-02-19 21:28:31
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
traP 作問ハッカソンコンテスト 002(day2) (順位表) の他の問題:

Problem Statement

There is a connected simple undirected graph $G = (V, E)$ with $N$ vertices and $K$ edges.
The vertices are numbered from $1$ to $N$ and the edges are numbered from $1$ to $K$. Edge $i$ connects the vertices numbered $u_i$ and $v_i$, and has a cost $w_i$ and a profit $p_i$.
For a spanning tree $T$ of $G$, let $I$ be the set of the numbers of its edges, and define the cost $W(T)$ and the profit $P(T)$ of $T$ as follows.

  • $\displaystyle W(T) = \sum_{i \in I} w_i$
  • $\displaystyle P(T) = \max_{i \in I}\ p_i$
That is, the cost of a spanning tree is the sum of the costs of its edges, and its profit is the maximum of the profits of its edges.
You are given the allowable cost $C$ of a spanning tree.
Among all $T$ satisfying $W(T) \leq C$, find and output the maximum value of $P(T)$.
If no such $T$ exists, output $-1$.

Input

$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)$
  • The given graph is a connected simple undirected graph.
  • All input values are integers.

Output

Output the maximum value of $P(T)$ among all $T$ satisfying the condition. If no $T$ satisfies the condition, output $-1$.

Sample

Sample 1
Input
3 3 1000
1 2 20 20
2 3 10 10
3 1 1 1
Output
20    

The input represents the following graph.



For this graph, consider the spanning tree $T$ consisting of the red edges in the figure below. It satisfies the cost condition $W(T) = 20 + 10 \leq 1000$,
and $P(T) = 20$, which is the maximum value.


Sample 2
Input
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
Output
4  
Sample 3
Input
3 3 1
1 2 100 100
2 3 100 100
3 1 100 100
Output
-1  

No spanning tree $T$ of this graph satisfies $W(T) \leq C$.

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