思路与算法

按输入小节及样例采用有向边。先从全0距离做Bellman-Ford判是否存在负环。若存在，用对角为0的最小加法邻接矩阵表示至多1条边，倍增平方直至出现负对角；再从高位到低位拼接仍无负对角的最大长度，答案加1。

正确性说明

最小加法乘积按中间点分解，矩阵幂给出至多指定边数的最短游走。对角为负等价该边数内有负闭游走。最短负闭游走若重复某点，可分成更短闭游走，其中至少一段为负，矛盾，故它是简单负环，边数即顶点数。负对角谓词随长度单调，倍增贪心找到第一次出现位置。

复杂度

Bellman-Ford O(NM)，最小加法倍增及组合O(N³logN)，矩阵初始化O(N²logN)，空间O(N²logN+M)。

易错点

原描述误写无向，包内保留原文并解释有向证据。无负环输出原题约定值。INF参与相加前两边都须判有限，不能把不可达与负边相加变成伪路径。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
using Mat = vector<int>;
Mat mul(const Mat &a, const Mat &b, int n) {
    Mat c(n * n, INF);
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++)
            if (a[i * n + k] < INF) {
                int x = a[i * n + k];
                int *out = &c[i * n];
                const int *row = &b[k * n];
                for (int j = 0; j < n; j++)
                    if (row[j] < INF)
                        out[j] = min(out[j], x + row[j]);
            }
    return c;
}
bool neg(const Mat &a, int n) {
    for (int i = 0; i < n; i++)
        if (a[i * n + i] < 0)
            return true;
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    Mat a(n * n, INF);
    for (int i = 0; i < n; i++)
        a[i * n + i] = 0;
    vector<tuple<int, int, int>> e;
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        --u;
        --v;
        a[u * n + v] = min(a[u * n + v], w);
        e.emplace_back(u, v, w);
    }
    vector<int> d(n);
    bool changed = false;
    for (int k = 0; k < n; k++) {
        changed = false;
        for (auto x : e) {
            int u, v, w;
            tie(u, v, w) = x;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                changed = true;
            }
        }
        if (!changed)
            break;
    }
    if (!changed) {
        cout << 0 << '\n';
        return 0;
    }
    vector<Mat> p(1, a);
    while (!neg(p.back(), n))
        p.push_back(mul(p.back(), p.back(), n));
    Mat f(n * n, INF);
    for (int i = 0; i < n; i++)
        f[i * n + i] = 0;
    int used = 0;
    for (int k = (int)p.size() - 2; k >= 0; k--) {
        Mat g = mul(f, p[k], n);
        if (!neg(g, n)) {
            f.swap(g);
            used += 1 << k;
        }
    }
    cout << used + 1 << '\n';
}