求助,tarjan放全局ac了,放std::function就wa了
查看原帖
求助,tarjan放全局ac了,放std::function就wa了
544909
heixiuxiu楼主2022/5/30 08:44

这个是开全局的tarjan,ac了

//
// Created by mrx on 2022/5/28.
//

#include <bits/stdc++.h>

#define ll long long
#define endl '\n'
const int N = 5e5 + 100;

std::vector<int> G[N];
bool inStack[N];
int dfn[N], low[N];
int f[N], val[N], wei[N];
std::stack<int> s;
int id = 0, scc = 1;

void tarjan(int u) {
    low[u] = dfn[u] = id++;
    s.push(u), inStack[u] = true;
    for (auto v: G[u]) {
        if (dfn[v] == -1) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if (inStack[v]) {
            low[u] = std::min(low[u], low[v]);
        }
    }
    if (dfn[u] == low[u]) {
        while (s.top() != u) {
            auto x = s.top();
            s.pop();
            inStack[x] = false;
            f[x] = scc;
            val[scc] += wei[x];
        }
        s.pop();
        inStack[u] = false;
        f[u] = scc;
        val[scc] += wei[u];
        scc++;
    }
};

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
#ifdef ONLINE_JUDGE
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#endif
    int n, m;
    std::cin >> n >> m;

    memset(f, 0, sizeof(f));
    memset(wei, 0, sizeof(wei));
    memset(val, 0, sizeof(val));
    memset(dfn, -1, sizeof(dfn));
    memset(low, -1, sizeof(low));

    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        G[u].push_back(v);
    }

    for (int i = 0; i < n; ++i) {
        std::cin >> wei[i];
    }

    int S, bar;
    std::cin >> S >> bar;
    S--;

    std::vector<int> isBar(n, 0);

    for (int i = 0; i < bar; ++i) {
        int x;
        std::cin >> x;
        x--;
        isBar[x] = 1;
    }

    tarjan(S);

    std::vector<std::vector<int>> G_new(scc);

    std::queue<int> q;
    std::vector<int> in(scc, 0);
    for (int i = 0; i < n; ++i) {
        for (auto v: G[i]) {
            if (f[i])
                if (f[i] != f[v]) {
                    G_new[f[i]].push_back(f[v]);
                    in[f[v]]++;
                }
        }
    }

    q.push(f[S]);
//    std::cerr << in[f[S]] << endl;
    std::vector<int> dp(scc, 0);
    dp[f[S]] = val[f[S]];

    while (!q.empty()) {
        auto now = q.front();
        q.pop();
        for (auto v: G_new[now]) {
            dp[v] = std::max(dp[v], dp[now] + val[v]);
            if (!(--in[v]))q.push(v);
        }
    }

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (isBar[i]) {
            ans = std::max(ans, dp[f[i]]);
        }
    }

    std::cout << ans << endl;
    return 0;
}

但是放在std::function就mle+wa了,救救孩子

//
// Created by mrx on 2022/5/28.
//

#include <bits/stdc++.h>

#define ll long long
#define endl '\n'

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
#ifdef ONLINE_JUDGE
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#endif
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> G(n);
    std::vector<int> f(n, 0), val(n, 0), wei(n, 0);
    std::vector<int> low(n, -1), dfn(n, -1);
    std::vector<int> inStack(n, 0);
    std::stack<int> s;
    int id = 0, scc = 0;
    std::function<void(int)> tarjan = [&](int u) -> void {
        low[u] = dfn[u] = ++id;
        inStack[u] = 1, s.push(u);
        for (auto v: G[u]) {
            if (dfn[v] == -1) {
                tarjan(v);
                low[u] = std::min(low[u], low[v]);
            } else if (inStack[v]) {
                low[u] = std::min(low[u], low[v]);
            }
        }
        if (low[u] == dfn[u]) {
            while (s.top() != u) {
                f[s.top()] = scc;
                val[scc] += wei[s.top()];
                inStack[s.top()] = 0;
                s.pop();
            }
            f[s.top()] = scc;
            val[scc] += wei[s.top()];
            inStack[s.top()] = 0;
            s.pop();
            scc++;
        }
    };

    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        G[u].push_back(v);
    }

    for (int i = 0; i < n; ++i) {
        std::cin >> wei[i];
    }

    int S, bar;
    std::cin >> S >> bar;
    S--;

    std::vector<int> isBar(n, 0);

    for (int i = 0; i < bar; ++i) {
        int x;
        std::cin >> x;
        x--;
        isBar[x] = 1;
    }

    tarjan(S);

    std::vector<std::vector<int>> G_new(scc);

    std::queue<int> q;
    std::vector<int> in(scc, 0);
    for (int i = 0; i < n; ++i) {
        for (auto v: G[i]) {
            if (f[i])
                if (f[i] != f[v]) {
                    G_new[f[i]].push_back(f[v]);
                    in[f[v]]++;
                }
        }
    }

    q.push(f[S]);
    std::vector<int> dp(scc, 0);
    dp[f[S]] = val[f[S]];

    while (!q.empty()) {
        auto now = q.front();
        q.pop();
        for (auto v: G_new[now]) {
            dp[v] = std::max(dp[v], dp[now] + val[v]);
            if (!(--in[v]))q.push(v);
        }
    }

    int ans = -1;
    for (int i = 0; i < n; ++i) {
        if (isBar[i]) {
            ans = std::max(ans, dp[f[i]]);
        }
    }

    std::cout << ans << endl;
    return 0;
}
2022/5/30 08:44
加载中...