记录编号	577861	评测结果	AAAAAAAAAAA
题目名称	[USACO22 Open Silver]Visits	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.809 s
提交时间	2022-11-25 19:14:05	内存使用	0.00 MiB

#include "bits/stdc++.h"

using i64 = long long;

int main() {
    freopen("prob1_silver_22open.in", "r", stdin); 
    freopen("prob1_silver_22open.out", "w", stdout);
    
    int n;
    std::cin >> n;

    std::vector<i64> a(n + 1), v(n + 1), ind(n + 1);
    std::map<int, bool> st;

    for (int i = 1; i <= n; ++ i) {
        std::cin >> a[i] >> v[i];
        ++ ind[a[i]];
    }

    i64 res = 0;

    auto toposort = [&] () {
        std::queue<int> q;
        for (int i = 1; i <= n; ++ i) {
            if (ind[i] == 0) q.push(i);
        }

        while (q.size()) {
            int t = q.front(); q.pop();

            res += v[t], st[t] = true;

            if (-- ind[a[t]] == 0) {
                q.push(a[t]);
            }
        }
    };

    std::function<i64(i64)> dfs = [&] (i64 u) {
        if (!st[u]) {
            st[u] = true;
            return std::min(v[u], dfs(a[u]));
        }
        return LONG_LONG_MAX;
    };

    toposort();

    for (int i = 1; i <= n; ++ i) {
        if (!st[i]) res += v[i]; 
    }

    for (int i = 1; i <= n; ++ i) {
        if (!st[i]) {
            res -= dfs(i), st[i] = true;
        }
    }

    std::cout << res << '\n';
    return 0;
}