#include #define rep(i,a,b) for(int i=a;i struct SCC { vector > SC; int NV, GR[MV], rev[MV]; vector E[MV], RE[MV], NUM; int vis[MV]; void init(int NV) { this->NV = NV; for (int i = 0; i= 0; i--) if (!vis[NUM[i]]) { SC[c].clear(); revdfs(NUM[i], c); sort(SC[c].begin(), SC[c].end()); c++;} SC.resize(c); }}; struct TopologicalSort { vector> E; TopologicalSort(int N) { E.resize(N); } void add_edge(int a, int b) { E[a].insert(b); } bool visit(int v, vector& order, vector& color) { color[v] = 1; for (int u : E[v]) { if (color[u] == 2) continue; if (color[u] == 1) return false; if (!visit(u, order, color)) return false; } order.push_back(v); color[v] = 2; return true; } bool sort(vector &order) { int n = E.size(); vector color(n); for (int u = 0; u < n; u++) if (!color[u] && !visit(u, order, color)) return false; reverse(order.begin(), order.end()); return true; } }; /*---------------------------------------------------------------------------------------------------             ∧_∧       ∧_∧  (´<_` )  Welcome to My Coding Space!      ( ´_ゝ`) /  ⌒i     /   \    | |     /   / ̄ ̄ ̄ ̄/  |   __(__ニつ/  _/ .| .|____      \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ int N, L[101], S[101]; vector P[101]; int vis[101]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) cin >> L[i] >> S[i]; SCC<101> scc; scc.init(N); rep(i, 0, N) if (S[i] - 1 != i) scc.add_edge(S[i] - 1, i); scc.scc(); rep(i, 0, N) P[scc.GR[i]].push_back(L[i]); rep(i, 0, N) sort(P[i].begin(), P[i].end()); TopologicalSort ts(101); rep(i, 0, N) { int a = scc.GR[S[i] - 1]; int b = scc.GR[i]; if (a != b) scc.add_edge(a, b); } vector order; ts.sort(order); int ans = 0; for (auto i : order) { for (auto j : P[i]) ans += j; if (!vis[i] && P[i].size()) ans += P[i][0]; for (int j : ts.E[i]) vis[j] = 1; } printf("%d", ans / 2); if (ans % 2) printf(".5"); else printf(".0"); printf("\n"); }