#include #include using namespace std; typedef vector > matrix; typedef int weight; const int inf = 1 << 30; /* FROM Spaghetti Source */ void backward_traverse(int v, int s, int r, matrix &g, vector &no, vector< vector > &comp, vector &prev, vector &mcost, vector &mark, weight &cost, bool &found) { const int n = g.size(); if (mark[v]) { vector temp = no; found = true; do { cost += mcost[v]; v = prev[v]; if (v != s) { while (comp[v].size() > 0) { no[comp[v].back()] = s; comp[s].push_back(comp[v].back()); comp[v].pop_back(); } } } while (v != s); for (int j = 0; j < n; ++j) if (j != r && no[j] == s) for (int i = 0; i < n; ++i) if (no[i] != s && g[i][j] < inf) g[i][j] -= mcost[ temp[j] ]; } mark[v] = true; for (int i = 0; i < n; ++i) if (no[i] != no[v] && prev[ no[i] ] == v) if (!mark[ no[i] ] || i == s) backward_traverse(i, s, r, g, no, comp, prev, mcost, mark, cost, found); } weight minimum_spanning_arborescence(int r, matrix &g) { const int n = g.size(); vector no(n); vector< vector > comp(n); for (int i = 0; i < n; ++i) { no[i] = i; comp[i].push_back(i); } weight cost = 0; while (1) { vector prev(n, -1); vector mcost(n, inf); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (j == r) continue; if (no[i] != no[j] && g[i][j] < inf) { if (g[i][j] < mcost[ no[j] ]) { mcost[ no[j] ] = g[i][j]; prev[ no[j] ] = no[i]; } } } } bool stop = true; vector mark(n); for (int i = 0; i < n; ++i) { if (i == r || mark[i] || comp[i].size() == 0) continue; bool found = false; backward_traverse(i, i, r, g, no, comp, prev, mcost, mark, cost, found); if (found) stop = false; } if (stop) { for (int i = 0; i < n; ++i) if (prev[i] >= 0) cost += mcost[i]; return cost; } } } int main() { int32_t N; cin >> N; matrix M(N + 1, vector(N + 1, inf)); int L[N], S[N]; for(int i = 0; i < N; i++) { cin >> L[i] >> S[i]; M[0][i + 1] = L[i] * 2; M[S[i]][i + 1] = L[i]; } cout << minimum_spanning_arborescence(0, M) * 0.5 << endl; }