No.2642 Don't cut line!
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$
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
abap34
noya2