＂中国东信杯＂广西大学第二届程序设计竞赛 - H - Antinomy与伊尔美格

题意：给一个有向图，n个点m条边，每个点有点权xi。规定从u点出发，到指定的k个点之一结束，可以多次经过同一个点和同一条边，求路径上点权和的最大值。

题解：直接缩点变成DAG，然后dp的时候并不是直接往父亲上面加，比如下面的4个点4条边的图：

4 4
1 2
1 3
2 4
3 4

直接往父亲上面加会导致x[4]出现了两次。

注意到这个其实是DAG，拓扑的时候把自己的值尝试更新给父亲，父亲保留所有儿子之中的最大值就可以了。

又交又WA，忘记考虑结束点的情况了。只有当这个儿子的答案中携带结束点的时候才往父亲更新，同时设置父亲的答案也是携带有结束点。

又交又T，板子里有个排序去重，5e5居然不能nlogn，好吧，それは私の過ちです。

namespace SCC {
    const int MAXN = 5e5;

    int n;
    vector<int> G[MAXN + 5], BG[MAXN + 5];

    int c1[MAXN + 5], cntc1;
    int c2[MAXN + 5], cntc2;
    int s[MAXN + 5], cnts;

    int n2;
    vector<int> V2[MAXN + 5];
    vector<int> G2[MAXN + 5], BG2[MAXN + 5];

    int val[MAXN + 5];
    ll val2[MAXN + 5];
    bool ok[MAXN + 5];
    bool ok2[MAXN + 5];

    void Init(int _n) {
        n = _n;
        cntc1 = 0, cntc2 = 0, cnts = 0;
        for(int i = 1; i <= n; ++i) {
            G[i].clear();
            BG[i].clear();
            c1[i] = 0;
            c2[i] = 0;
            s[i] = 0;
            V2[i].clear();
            G2[i].clear();
            BG2[i].clear();
            val[i] = 0;
            val2[i] = 0;
            ok[i] = 0;
            ok2[i] = 0;
        }
    }

    void AddEdge(int u, int v) {
        G[u].push_back(v);
        BG[v].push_back(u);
    }

    void dfs1(int u) {
        c1[u] = cntc1;
        for(int v : G[u]) {
            if(!c1[v])
                dfs1(v);
        }
        s[++cnts] = u;
    }

    void dfs2(int u) {
        V2[cntc2].push_back(u);
        val2[cntc2] += val[u];
        ok2[cntc2] |= ok[u];
        c2[u] = cntc2;
        for(int v : BG[u]) {
            if(!c2[v])
                dfs2(v);
        }
    }

    void Kosaraju() {
        for(int i = 1; i <= n; ++i) {
            if(!c1[i]) {
                ++cntc1;
                dfs1(i);
            }
        }

        for(int i = n; i >= 1; --i) {
            if(!c2[s[i]]) {
                ++cntc2;
                dfs2(s[i]);
            }
        }
    }

    void Build() {
        n2 = cntc2;
        for(int i = 1; i <= n2; ++i) {
            for(auto u : V2[i]) {
                for(auto v : G[u]) {
                    if(c2[v] != i) {
                        G2[i].push_back(c2[v]);
                        BG2[c2[v]].push_back(i);
                    }
                }
            }
        }

        for(int i = 1; i <= n2; ++i) {
            //sort(G2[i].begin(), G2[i].end());
            //G2[i].erase(unique(G2[i].begin(), G2[i].end()), G2[i].end());
            //sort(BG2[i].begin(), BG2[i].end());
            //BG2[i].erase(unique(BG2[i].begin(), BG2[i].end()), BG2[i].end());
        }
    }


    queue<int> Q;
    int outdeg[MAXN + 5];
    ll dp[MAXN + 5];
    bool ok3[MAXN + 5];
    void Solve(int u) {
        for(int i = 1; i <= n2; ++i) {
            if(G2[i].size() == 0)
                Q.push(i);
            outdeg[i] = G2[i].size();
            dp[i] = 0;
            ok3[i] = ok2[i];
        }
        while(!Q.empty()) {
            int u = Q.front();
            Q.pop();
            if(ok3[u])
                dp[u] += val2[u];
            for(auto v : BG2[u]) {
                if(ok3[u]) {
                    dp[v] = max(dp[v], dp[u]);
                    ok3[v] = 1;
                }
                outdeg[v]--;
                if(outdeg[v] == 0)
                    Q.push(v);
            }
        }
        u = c2[u];
        printf("%lld\n", dp[u]);
    }
}

void test_case() {
    int n, m;
    scanf("%d%d", &n, &m);
    SCC::Init(n);
    while(m--) {
        int u, v;
        scanf("%d%d", &u, &v);
        SCC::AddEdge(u, v);
    }
    for(int i = 1; i <= n; ++i)
        scanf("%d", &SCC::val[i]);
    int u, k;
    scanf("%d%d", &u, &k);
    while(k--) {
        int v;
        scanf("%d", &v);
        SCC::ok[v] = 1;
    }
    SCC::Kosaraju();
    SCC::Build();
    SCC::Solve(u);
}