Description

找最小的正环

Solution

用 找环, 令 是经过 条边, 从 到 的距离
易得, 是中间点,时间复杂度
只需找到一个 的点即可
考虑倍增优化 表示经过 条边, 从 到 的距离
二进制贪心枚举, 找到最小符合条件的边数

Code

#include<bits/stdc++.h>
const int N = 5e5 + 5;
typedef long long ll;

__int32 f[15][305][305], dp[305][305], now[305][305];

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
  memset(now, 0xcf, sizeof(now));
  memset(f, 0xcf, sizeof(f));
  __int32 n, m, ans = 0; std::cin >> n >> m;
  for(__int32 i = 1; i <= m; i++) {
    __int32 u, v; std::cin >> u >> v;
    std::cin >> f[0][u][v] >> f[0][v][u];
  }
  for(__int32 i = 1; i <= n; i++) {
    now[i][i] = 0, f[0][i][i] = 0;
  }
  for(__int32 t = 1; t <= 9; t++) {
    for(__int32 k = 1; k <= n; k++) {
      for(__int32 i = 1; i <= n; i++) {
        for(__int32 j = 1; j <= n; j++) {
          f[t][i][j] = std::max(f[t][i][j], f[t - 1][i][k] + f[t - 1][k][j]); // 预处理距离
        }
      }
    }
  }
  for(__int32 t = 9; t >= 0; --t) {
    memset(dp, 0xcf, sizeof(dp));
    for(__int32 k = 1; k <= n; k++) {
      for(__int32 i = 1; i <= n; i++) {
        for(__int32 j = 1; j <= n; j++) {
          dp[i][j] = std::max(dp[i][j], now[i][k] + f[t][k][j]); // dp[i][j] 是当前2^t 边数的状态
        }
      }
    }
    bool f = false;
    for(__int32 i = 1; i <= n; i++) {
      if(dp[i][i] > 0) {
        f = true;
        break;
      }
    }
    if(f) continue; // 有环了 这个2^t 不考虑
    else { // 无环 要加上这些边, 即把状态更新进入下一次枚举
      for(__int32 i = 1; i <= n; i++) {
        for(__int32 j = 1; j <= n; j++) {
          now[i][j] = dp[i][j];
        }
      }
      ans |= (1 << t);
    }
  } 
  ans = ans >= n ? 0 : ans + 1; // 最终答案加1才是最小次数
  std::cout << ans << '\n';
  return 0;
}