dp+倍增优化
求最小正环，看到数据范围小，考虑 dp。设 \(f_{k,i,j}\) 表示走不超过 \(k\) 条边，\(i\) 走到 \(j\) 得到的最大权值。转移类似 floyd。答案是最小的 \(k\) 存在 \(f_{k,i,j}>0\)，复杂度是 \(O(n^4)\)。
考虑优化状态的表示，记录边数这一维可以用倍增优化。将 \(f_{k,i,j}\) 表示为走不超过 \(2^k\) 条边，\(i\) 走到 \(j\) 得到的最大权值。转移简单。难点在求出答案，这时考虑贪心，从大到小枚举 \(k\)，维护一个 \(g_{i,j}\) 表示当前走的边数为 \(ans\) 的状态，此时用 \(f_{k,i,j}\) 转移 \(g\)，如果仍然没有最小正环，那么 \(ans\) 加上 \(2^k\)；否则继续往下枚举 \(k\)。
复杂度 \(O(n^3\log n)\)。
typedef long long i64;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 310;
int n, m, ans;
int f[10][N][N], tmp[N][N], lst[N][N];
void Solve() {
memset(f, -0x3f, sizeof(f));
std::cin >> n >> m;
for(int i = 1; i <= m; i++) {
int x, y, z, w;
std::cin >> x >> y >> z >> w;
f[0][x][y] = z, f[0][y][x] = w;
}
for(int i = 1; i <= n; i++) f[0][i][i] = 0;
for(int s = 1; s <= 9; s++) {
for(int k = 1; k <= n; k++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
f[s][i][j] = std::max(f[s][i][j], f[s - 1][i][k] + f[s - 1][k][j]);
}
}
}
}
memset(lst, -0x3f, sizeof(lst));
for(int i = 1; i <= n; i++) lst[i][i] = 0;
for(int s = 9; s >= 0; s--) {
memset(tmp, -0x3f, sizeof(tmp));
for(int k = 1; k <= n; k++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
tmp[i][j] = std::max(tmp[i][j], lst[i][k] + f[s][k][j]);
}
}
}
bool flg = 0;
for(int i = 1; i <= n; i++) {
if(tmp[i][i] > 0) {
flg = 1;
}
}
if(!flg) {
ans += (1 << s);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) lst[i][j] = tmp[i][j];
}
}
}
std::cout << (ans >= n ? 0 : ans + 1) << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Solve();
return 0;
}