洛谷P3387 【テンプレート】縮点

洛谷 P3387 【テンプレート】縮点#

大佬のコードと比較してエラーを引き出したとき、以前にそんなに多くの点を通過できたのはまさに奇跡だと感じました。

题面#

n 個の点と m 本の辺を持つ有向グラフが与えられ、各点には重みがあり、通過する点の重みの合計が最大になるような経路を求めます。この重みの合計を求めてください。

辺や点を複数回通過することが許可されていますが、重複して通過する点の重みは 1 回だけ計算されます。

入力形式：

1 行目、n,m

2 行目、n 個の整数、順に点の重みを表します。

3 行目から m+2 行目まで、各行に 2 つの整数 u,v があり、u->v に有向辺があることを示します。

出力形式：

1 行で、最大の点の重みの合計を出力します。

n<=10^4,m<=10^5,0<= 点重み <=1000

思路#

またしても長い間書かれたテンプレート問題です。
tarjan 縮点 + DAG dp という私が聞いたことのない操作です。。
（または + メモ化探索でも良いです）
今後はグラフを struct として書くことはありません、せいぜい namespace の中に書くだけです！！！
重複辺はトポロジカルソートに影響を与えません
ここでの tarjan では、強連結成分のノードを探索木の根ノードの番号で色付けすることで、この i が本当に入度がないのか、そもそもグラフに存在しないのかを判断するのに役立ちます。

コード#

#include<cstdio>
#include<iostream>
#include<stack>
#include<queue>
using namespace std;

const int MAXN = 1e5 + 5;

int n, m;

class Tu {
public:
    struct ed {
        int to;
        int nex;
    };
    void insert (int p1, int p2) {
        ++newp;
        e[newp].to = p2;
        e[newp].nex = head[p1];
        head[p1] = newp;
    }

    int& operator[] (int &p) {
        return w[p];
    }

    void tarjan (int p) {
        dfn[p] = low[p] = ++tim;
        s.push(p);
        v[p] = 1;
        for (int i = head[p]; i; i = e[i].nex) {
            int y = e[i].to;
            if (!dfn[y]) {
                tarjan(y);
                low[p] = min(low[p], low[y]);
            }
            else if (v[y]) {
                low[p] = min(low[p], dfn[y]);
            }
        }
        if (dfn[p] == low[p]) {
            v[p] = 0;
            color[p] = p;
            while (s.top() != p) {
                int y = s.top();
                s.pop();
                color[y] = p;
            }
            s.pop();
        }
    }

    int topsort(int *cl) {
        queue<int> q;
        for (int i = 1; i <= n; ++i) {
            if (cl[i] == i && !in[i]) {
                q.push(i);
                f[i] = w[i];
            }
        }
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int i = head[u]; i; i = e[i].nex) {
                int y = e[i].to;
                f[y] = max(f[y], f[u] + w[y]);
                if (--in[y] == 0) {
                    q.push(y);
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans = max(f[i], ans);
        }
        return ans;
    }

    ed e [MAXN];
    int head[MAXN];
    int newp, cnt;
    int w[MAXN];
    int color[MAXN];
    int dfn[MAXN], low[MAXN], tim;
    int out[MAXN], f[MAXN], in[MAXN];
    bool v[MAXN];
    stack<int> s;
} a, b;


int main (void) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= m; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        a.insert(x, y);
    }
    for (int i = 1; i <= n; ++i) {
        if (!a.color[i]) a.color[i] = i;
        if (!a.dfn[i]) {
            a.tarjan(i);
        }
    }

    for (int i = 1; i <= n; ++i) {
        int u = a.color[i];
        for (int j = a.head[i]; j; j = a.e[j].nex) {
            int y = a.color[a.e[j].to];
            if (u == y) continue;
            b.insert(u, y);
            ++b.in[y];
        }
    }
    for (int i = 1; i <= n; ++i) {
        b.w[a.color[i]] += a.w[i];
    }
    printf("%d\n", b.topsort(a.color));
    return 0;
}