洛谷P3387 【模板】缩点

同步：https://hexo.buringstraw.win/2019/07/21/洛谷P3387-【模板】缩点/
https://buringstraw.win/index.php/archives/45/

当我对比大佬的代码调出错误之后，我不禁觉得我之前能过那么多个点简直就是个奇迹

题面

给定一个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;
}

洛谷P3387 【模板】缩点

原文：https://www.cnblogs.com/buringstraw/p/11222679.html