Luogu P3387 [Template] Shrinking Nodes

Luogu P3387 [Template] Shrink Points#

When I compared my code with the code of the big shots and found an error, I couldn't help but feel that it was a miracle that I was able to pass so many test cases before.

Problem Description#

Given a directed graph with n vertices and m edges, each vertex has a weight. Find a path that maximizes the sum of the weights of the vertices on the path. You only need to output the maximum sum of weights.

Input format:

The first line contains two integers, n and m.

The second line contains n integers, representing the weights of the vertices.

The next m lines each contain two integers, u and v, indicating a directed edge from u to v.

Output format:

Output a single line, the maximum sum of weights.

n <= 10^4, m <= 10^5, 0 <= vertex weight <= 1000

Approach#

Another template problem that took me a long time to write. Tarjan's algorithm for shrinking points and DAG (Directed Acyclic Graph) dynamic programming, which I've never heard of before. (Or you can use memoization search.) I will never write a graph as a struct again, at most I will write it inside a namespace!!! Duplicate edges do not affect topological sorting. In this tarjan algorithm, coloring a node in a strongly connected component as the number of the root of the search tree helps determine whether i has no indegree or is not even in the graph when it enters the queue during topological sorting.

Code#

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

const int MAXN = 1e5 + 5;

int n, m;

class Graph {
public:
    struct Edge {
        int to;
        int next;
    };
    void insert (int p1, int p2) {
        ++newp;
        edges[newp].to = p2;
        edges[newp].next = head[p1];
        head[p1] = newp;
    }

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

    void tarjan (int p) {
        dfn[p] = low[p] = ++tim;
        s.push(p);
        visited[p] = 1;
        for (int i = head[p]; i; i = edges[i].next) {
            int y = edges[i].to;
            if (!dfn[y]) {
                tarjan(y);
                low[p] = min(low[p], low[y]);
            }
            else if (visited[y]) {
                low[p] = min(low[p], dfn[y]);
            }
        }
        if (dfn[p] == low[p]) {
            visited[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 && !indegree[i]) {
                q.push(i);
                f[i] = weights[i];
            }
        }
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int i = head[u]; i; i = edges[i].next) {
                int y = edges[i].to;
                f[y] = max(f[y], f[u] + weights[y]);
                if (--indegree[y] == 0) {
                    q.push(y);
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans = max(f[i], ans);
        }
        return ans;
    }

    Edge edges [MAXN];
    int head[MAXN];
    int newp, cnt;
    int weights[MAXN];
    int color[MAXN];
    int dfn[MAXN], low[MAXN], tim;
    int outdegree[MAXN], f[MAXN], indegree[MAXN];
    bool visited[MAXN];
    stack<int> s;
} graph_a, graph_b;


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

    for (int i = 1; i <= n; ++i) {
        int u = graph_a.color[i];
        for (int j = graph_a.head[i]; j; j = graph_a.edges[j].next) {
            int y = graph_a.color[graph_a.edges[j].to];
            if (u == y) continue;
            graph_b.insert(u, y);
            ++graph_b.indegree[y];
        }
    }
    for (int i = 1; i <= n; ++i) {
        graph_b.weights[graph_a.color[i]] += graph_a.weights[i];
    }
    printf("%d\n", graph_b.topsort(graph_a.color));
    return 0;
}