骑士(Knights) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> w(n + 1);
    vector<int> hate(n + 1), indeg(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> w[i] >> hate[i];
        indeg[hate[i]]++;
    }
    vector<long long> dp0(n + 1, 0), dp1(n + 1, 0);
    for (int i = 1; i <= n; ++i) dp1[i] = w[i];
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (indeg[i] == 0) q.push(i);
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        int p = hate[u];
        dp0[p] += max(dp0[u], dp1[u]);
        dp1[p] += dp0[u];
        if (--indeg[p] == 0) q.push(p);
    }
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (indeg[i] > 0) {
            vector<int> cyc;
            int cur = i;
            while (indeg[cur] > 0) {
                indeg[cur] = 0;
                cyc.push_back(cur);
                cur = hate[cur];
            }
            int k = (int)cyc.size();
            long long best = 0;
            // Case 1: cyc[0] not taken
            long long f0 = dp0[cyc[0]], f1 = -(1LL << 58);
            for (int j = 1; j < k; ++j) {
                int v = cyc[j];
                long long nf0 = max(f0, f1) + dp0[v];
                long long nf1 = f0 + dp1[v];
                f0 = nf0;
                f1 = nf1;
            }
            best = max(best, max(f0, f1));
            // Case 2: cyc[0] taken -> cyc[k-1] cannot be taken
            f0 = -(1LL << 58);
            f1 = dp1[cyc[0]];
            for (int j = 1; j < k; ++j) {
                int v = cyc[j];
                long long nf0 = max(f0, f1) + dp0[v];
                long long nf1 = f0 + dp1[v];
                f0 = nf0;
                f1 = nf1;
            }
            best = max(best, f0);
            ans += best;
        }
    }
    cout << ans << "\n";
    return 0;
}