题目
思考
这里转为判定负环可以是可以，但是不能用超级源点了（改为把节点全部压入），因为按照题目条件，建立的应该是各个节点指向超级源点的有向边，这显然破坏了超级源点的功能
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10, M = 3 * N;
int h[N], e[M], ne[M], idx, w[M];
int pre[N], col[N], cnt;
bool st[N];
int dist[N];
int q[N];
int n, k, hh, tt = -1;
ll ans;
void add(int a, int b, int c) // 添加一条边a->b，边权为c
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
bool dfs(int u)
{if(col[u]) return col[u] == 2;col[u] = 2;if(~pre[u] && dfs(pre[u])) return true;col[u] = 1;return false;
}
bool check()
{memset(col, 0, sizeof col);for(int i = 0; i <= n; i++)if(!col[i] && dfs(i)) return true;return false;
}
bool spfa()
{memset(pre, -1, sizeof pre);memset(dist, -0x3f, sizeof dist);q[++tt] = 0, dist[0] = 0, st[0] = 1;while(hh <= tt){int u = q[tt--];st[u] = 0;for(int i = h[u]; ~i; i = ne[i]){int j = e[i];if(dist[j] < dist[u] + w[i]){dist[j] = dist[u] + w[i];pre[j] = u;if(++cnt > n) {cnt = 0;if(check()) return false;}if(!st[j])q[++tt] = j, st[j] = 1;}}}for(int i = 1; i <= n; i++)ans += dist[i];return true;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cin >> n >> k;memset(h, -1, sizeof h);for(int i = 1; i <= k; i++){int x, a, b;cin >> x >> a >> b;if(x == 1) add(a, b, 0), add(b, a, 0);else if(x == 2) add(a, b, 1);else if(x == 3) add(b, a, 0);else if(x == 4) add(b, a, 1);else add(a, b, 0);}for(int i = 1; i <= n; i++)add(0, i, 1);if(!spfa()) cout << "-1";else cout << ans;
}
