博客地址: https://blog.csdn.net/qq_41280600/article/details/104175759

#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
typedef long long ll;
using namespace std;
const int N = 1e5 + 5, M = 3e5 + 5;
struct E {
    int v, w, next;
} e[M]; 
int n, m, u, v, x, len = 1, h[N], d[N], cnt[N];
bool vis[N];
void add(int u, int v, int w) {
    e[len].v = v;
    e[len].w = w;
    e[len].next = h[u];
    h[u] = len++;
}
bool spfa() {
    memset(d, -0x3f, sizeof(d));//最小值求最长路
    d[0] = 0; //0是超级源点 
    stack<int> q;
    q.push(0);
    while (!q.empty()) {
        int u = q.top();
        q.pop();
        vis[u] = false;
        for (int j = h[u]; j; j = e[j].next) {
            int v = e[j].v;
            int w = d[u] + e[j].w;
            if (w > d[v]) {
                d[v] = w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n + 1) return true; //有正环 且点数是n+1 加入了超级源点
                if (!vis[v]) q.push(v), vis[v] = true;
            }
        }
    } 
    return false;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &x, &u, &v);
        if (x == 1) add(u, v, 0), add(v, u, 0);
        else if (x == 2) add(u, v, 1); 
        else if (x == 3) add(v, u, 0); 
        else if (x == 4) add(v, u, 1); 
        else if (x == 5) add(u, v, 0); 
    }
    //添加超级源点
    for (int i = 1; i <= n; i++) add(0, i, 1);
    if (spfa()) printf("-1");
    else {
        ll ans = 0;
        for (int i = 1; i <= n; i++) ans += d[i];
        printf("%lld", ans);
    } 
    return 0;
}