洛谷P3387 【模板】縮點

洛谷 P3387 【模板】縮點#

當我對比大佬的代碼調出錯誤之後，我不禁覺得我之前能過那麼多個點簡直就是個奇蹟

題面#

給定一個 n 個點 m 條邊有向圖，每個點有一個權值，求一條路徑，使路徑經過的點權值之和最大。你只需要求出這個權值和。

允許多次經過一條邊或者一個點，但是，重複經過的點，權值只計算一次。

輸入格式：

第一行，n,m

第二行，n 個整數，依次代表點權

第三至 m+2 行，每行兩個整數 u,v，表示 u->v 有一條有向邊

輸出格式：

共一行，最大的點權之和。

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;
}