Tarjan+BFS+DP喜提MLE81,玄关
查看原帖
Tarjan+BFS+DP喜提MLE81,玄关
845400
lwj54joy楼主2025/6/28 17:13

rt,Tarjan缩点之后跑了一遍DP(准确的来说是BFS),然后喜提MLE81,MLE on #2#3#10,评测记录
本人调了一天已经快疯了 哪位好人救救俺。。玄关

/*
 * > CPP Code Snippet <
 * > Powered by Microsoft Visual Studio Code <
 *
 * @Author    FrankWKD (wangkedi01)
 * @Date      2025-06-28
 * @Network   "https://www.luogu.com.cn/problem/P3627"
 * @License   GNU General Public License 2.0
 * @Platform  [Frank]iMac Ubuntu Pro 24.04 LTS
 * @FileName  P3627-Tarjan.cpp
 * @FilePath  /media/frank/FrankW/_default/_Mine!/Working/code-spaces/Luogu/P3627-Tarjan.cpp
 * @Solution  同P3387,几乎是一个题,唯一要注意的就是这一题计算的是以s为起点的最长路,但是我们也可以用拓扑排序+dp的方法,因为缩点后的DAG是保证不存在环的,直接大胆dp就行。
 */

// #pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
struct node {
    int to, nxt;
} a[N], DAG[N];
int pre[N], pred[N], k, kd;
int n, m, s, p;
int x, y;
int dfn[N], low[N], si[N], id[N], times, sccnt;
int val[N], vald[N], dp[N];
bool pubd[N];
bool pub[N], inst[N];
stack<int> st;
inline void add(int u, int v) {
    a[++k] = {v, pre[u]};
    pre[u] = k;
}
inline void addDAG(int u, int v) {
    DAG[++kd] = {v, pred[u]};
    pred[u] = kd;
}
inline void tarjan(int x) {
    dfn[x] = low[x] = ++times;
    inst[x] = 1;
    st.push(x);
    for (int i = pre[x]; i; i = a[i].nxt) {
        int to = a[i].to;
        if (!dfn[to]) {
            tarjan(to);
            low[x] = min(low[to], low[x]);
        } else if (inst[to])
            low[x] = min(low[x], dfn[to]);
    }
    if (dfn[x] == low[x]) {
        int t;
        sccnt++;
        do {
            t = st.top();
            st.pop();
            si[sccnt]++;
            id[t] = sccnt;
            inst[t] = 0;
            vald[sccnt] += val[t];
            if (pub[t])
                pubd[sccnt] = 1;
        } while (t != x);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (register int i = 1; i <= m; i++) {
        cin >> x >> y;
        add(x, y);
    }
    for (register int i = 1; i <= n; i++) cin >> val[i];
    cin >> s >> p;
    for (register int i = 1; i <= p; i++) {
        cin >> x;
        pub[x] = 1;
    }

    tarjan(s);
    for (register int i = 1; i <= n; i++) {
        for (register int j = pre[i]; j; j = a[j].nxt) {
            int x = id[i];
            int y = id[a[j].to];
            if (x != y)
                addDAG(x, y);
        }
    }
    queue<int> q;
    q.push(id[s]);
    dp[id[s]] = vald[id[s]];
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        for (register int i = pred[t]; i; i = DAG[i].nxt) {
            dp[DAG[i].to] = max(dp[DAG[i].to], dp[t] + vald[DAG[i].to]);
            q.push(DAG[i].to);
        }
    }
    int ans = 0;
    for (register int i = 1; i <= sccnt; i++) {
        if (pubd[i] == 1)
            ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
}
2025/6/28 17:13
加载中...