問題一覧 > 通常問題

No.3079 Unite Japanese Prefectures

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が $10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : (AC するまで非表示) / 解いたユーザー数 37
作問者 : 👑 binap / テスター : Iroha_3856 👑 hamamu
お気に入りにしたユーザー ProblemId : 11967 / 自分の提出
問題文最終更新日: 2025-03-29 00:02:57
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
yukicoder contest 462 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。