No.3079 Unite Japanese Prefectures
タグ : / 解いたユーザー数 37
作問者 : 👑
Iroha_3856
👑
hamamu
Story
Let's connect Japan's $47$ prefectures with roads.
Problem Statement
There are $N$ regions, numbered from region $1$ to region $N$. Initially, there are no roads between these regions.
Using a ($6$-sided) die and a list containing $M$ triples of $3$ integers $(U_1, V_1, C_1), \cdots, (U_M, V_M, C_M)$, binap repeats the following series of operations until all regions can reach one another via roads.
Roll the die.
After checking the result of the roll, binap chooses an integer $i$ between $1$ and $M$, inclusive.
If the result of the roll is at least $C_i$, a bidirectional road connecting region $U_i$ and region $V_i$ is built.
binap's goal is to minimize the expected number of operations. Find the expected number of operations when binap continues to act optimally. It can be shown that under the constraints of this problem, the expected value is finite.
About the die
The die shows each integer from $1$ to $6$ with equal probability. Each roll is independent.
Constraints
$2\leq N \leq 47$
$\displaystyle N-1\leq M \leq \frac{N(N-1)}{2}$
$1 \leq U_i < V_i \leq N$ $(1\leq i \leq M)$
$(U_i,V_i) \neq (U_j,V_j)$ $( i \neq j )$
$1\leq C_i \leq 6$ $(1\leq i \leq M)$
If roads are built between region $U_i$ and region $V_i$ for all integers $i$ such that $i = 1,2,\cdots, M$, all regions can reach one another.
All input values are integers.
Input
$N$ $M$ $U_1$ $V_1$ $C_1$ $\vdots$ $U_M$ $V_M$ $C_M$
Output
Output on $1$ line the expected number of operations when binap acts optimally. Your answer is judged correct if its absolute or relative error from the intended solution is at most $10^{−6}$.
Sample
Sample 1
Input
3 3 1 2 1 1 3 2 2 3 3
Output
2.03333333333333
For example, the following sequence of events is possible.
・The result of the roll is $1$. Choose $i = 1$. A road connecting region $1$ and region $2$ is built.
・The result of the roll is $5$. Choose $i = 3$. A road connecting region $2$ and region $3$ is built. All regions can now reach one another, so the operations end.
In this case, the number of operations is $2$. When acting optimally for every possible outcome of the die rolls, the expected number of operations is $\displaystyle \frac{61}{30}$.
Sample 2
Input
2 1 1 2 1
Output
1
Regardless of the result of the roll, all regions can reach one another after $1$ operation.
1.000000
You may also output the answer in a form such as the above.
Sample 3
Input
5 6 2 4 5 4 5 4 1 2 6 1 4 4 2 5 4 3 4 2
Output
6.2592
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。