原题链接

题解

缩点+差分约束，求最小值故跑最长路

无解的情况：存在正权环，由于是有向图，所以环上的元素在一个强连通分量内，判断强连通分量内存不存在有正权值的边，然后缩点，拓扑跑一圈

缩点时要一个超级源点就可以只dfs一次了

code

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const ll MAXN = 100005;

vector<pair<ll, ll>> G[MAXN], E[MAXN];
ll vis[MAXN], dfn[MAXN], low[MAXN], belong[MAXN], in[MAXN], val[MAXN];
stack<ll> st;
ll cnt, num;

void dfs(ll now) {
    vis[now] = 1;
    dfn[now] = low[now] = ++cnt;
    st.push(now);

    for (auto next : G[now]) {
        ll to = next.first;
        if (!dfn[to]) {
            dfs(to);
            low[now] = min(low[now], low[to]);
        } else if (!belong[to]) {
            low[now] = min(low[now], dfn[to]);
        }
    }

    if (low[now] == dfn[now]) {
        ll x;
        num++;
        do {
            x = st.top();
            st.pop();
            belong[x] = num;
        } while (x != now);
    }
}

void solve() {
    ll n, k;
    cin >> n >> k;

    for (ll i = 1; i <= k; i++) {
        ll op, x, y;
        cin >> op >> x >> y;

        if (op == 1) {
            G[x].push_back({y, 0});
            G[y].push_back({x, 0});
        } else if (op == 2) {
            G[x].push_back({y, 1});
        } else if (op == 3) {
            G[y].push_back({x, 0});
        } else if (op == 4) {
            G[y].push_back({x, 1});
        } else {
            G[x].push_back({y, 0});
        }
    }

    for (ll i = 1; i <= n; i++) G[0].push_back({i, 1});
    dfs(0);

    bool flag = true;
    for (ll i = 1; i <= n; i++) {
        for (auto next : G[i]) {
            ll x = belong[i], y = belong[next.first];
            if (x == y && next.second != 0) {
                flag = false;
            }
            if (x != y) {
                E[x].push_back({y, next.second});
                in[y]++;
            }
        }
    }

    if (!flag) {
        cout << -1 << endl;
        return;
    }

    queue<ll> q;
    for (ll i = 1; i <= num; i++) {
        val[i] = 1;
        if (!in[i]) q.push(i);
    }

    while (!q.empty()) {
        ll now = q.front();
        q.pop();

        for (auto next : E[now]) {
            ll to = next.first;
            val[to] = max(val[to], val[now] + next.second);
            in[to]--;
            if (!in[to]) {
                q.push(to);
            }
        }
    }

    ll ans = 0;
    for(ll i = 1; i <= n; i++) {
        ans += val[belong[i]];
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    solve();
    return 0;
}