結果
問題 | No.3079 Unite Japanese Prefectures |
ユーザー |
![]() |
提出日時 | 2025-03-21 00:56:14 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 812 ms / 4,000 ms |
コード長 | 1,563 bytes |
コンパイル時間 | 3,885 ms |
コンパイル使用メモリ | 299,968 KB |
実行使用メモリ | 36,608 KB |
最終ジャッジ日時 | 2025-03-21 00:56:26 |
合計ジャッジ時間 | 11,030 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/dsu> #define rep(i, l, r) for (int i = (int)(l); i<(int)(r); i++) #define ll long long int main() { int N, M; cin >> N >> M; vector<tuple<int, int, int>> Edges(M); rep(i, 0, M) { int u, v, c; cin >> u >> v >> c; u--; v--; c--; Edges[i] = {c, u, v}; } array<int, 6> cnt = {0, 0, 0, 0, 0, 0}; atcoder::dsu d(N); sort(Edges.begin(), Edges.end()); for (int i = 0; i < M; i++) { auto[c, u, v] = Edges[i]; if (!d.same(u, v)) { d.merge(u, v); cnt[c]++; } } map<array<int, 6>, double> dp; //すでにこれだけ集めたときの残り回数の期待値 array<int, 6> A; #define FOR(x) for (A[x] = cnt[x]; A[x] >= 0; A[x]--) FOR(0) FOR(1) FOR(2) FOR(3) FOR(4) FOR(5) { #undef FOR int loop = 0; double t = 0; rep(i, 0, 6) { //iの目が出たとする //使える中で最上位に使うのが最適 bool used = false; array<int, 6> B = A; for (int j = i; j >= 0; j--) { if (B[j] < cnt[j]) { B[j]++; t += dp[B]; used = true; break; } } if (!used) loop++; } if (loop == 6) { dp[A] = 0; continue; } dp[A] = (t+6)/(6-loop); } cout << fixed << setprecision(15) << dp[{0, 0, 0, 0, 0, 0}] << endl; }