差分约束+ Tarjan 求强连通分量

首先根据差分约束的思想建图，发现应该求每个点的最长路，然后权值也只有 $\ge 0$ 的数
由于最长路里面不能存在正环，因此如果有环也只是零环，零环也就意味着环里面的每个点的糖果数是一样的，这样就可以使用 Tarjan 求强连通分量进行缩点，这样图就变成了一个 DAG ，使用 dp 求最长路即可

时间复杂度:$O(N+K)$

代码如下：

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 100010, M = N * 3;

int n, k;
int h[N], e[M << 1], ne[M << 1], w[M << 1], idx = 0, nh[N];
int dfn[N], low[N], timestamp = 0;
int id[N], val[N], sz[N], scc_cnt = 0;
int stk[N], tt = 0;
bool in_stk[N];
LL f[N];

void add(int h[], int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u) {
    dfn[u] = low[u] = ++ timestamp;
    stk[tt ++ ] = u, in_stk[u] = true;

    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stk[v]) low[u] = min(low[u], dfn[v]);
    }

    if (dfn[u] == low[u]) {
        ++ scc_cnt;
        int y;
        do {
            y = stk[ -- tt];
            in_stk[y] = false;
            id[y] = scc_cnt;
            sz[scc_cnt] ++ ;
        } while (y != u);
    }
}

LL dp() {
    for (int i = 0; i <= n; i ++ )
        for (int j = h[i]; ~j; j = ne[j]) {
            int a = id[i], b = id[e[j]];
            if (a == b) {
                val[a] += w[j];
                if (val[a] > 0) return -1;
            } else {
                add(nh, a, b, w[j]);
            }
        }
    f[scc_cnt] = 0;
    for (int i = scc_cnt; i >= 0; i -- ) {
        for (int j = nh[i]; ~j; j = ne[j]) {
            int v = e[j];
            f[v] = max(f[v], f[i] + w[j]);
        }
    }

    LL res = 0;
    for (int i = 1; i <= scc_cnt; i ++ )
        res = res + 1ll * sz[i] * f[i];
    return res;
}

int main() {
    memset(h, -1, sizeof h);
    memset(nh, -1, sizeof nh);
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ) add(h, 0, i, 1);
    while (k -- ) {
        int x, a, b; cin >> x >> a >> b;
        if (x == 1) {
            add(h, a, b, 0), add(h, b, a, 0);
        } else if (x == 2) {
            add(h, a, b, 1);
        } else if (x == 3) {
            add(h, b, a, 0);
        } else if (x == 4) {
            add(h, b, a, 1);
        } else if (x == 5) {
            add(h, a, b, 0);
        }
    }

    tarjan(0);
    cout << dp() << endl;
    return 0;
}