这道题网络流里的 dis 数组类型是 double，在 spfa 或者 dfs 的时候对 dis 大小的比较一定要用 eps。

比如

错误的代码（会 TLE on 9 or TLE on 23）：

bool spfa() {
  fill(d + 1, d + 1 + SN, INF);
  fill(vis + 1, vis + 1 + SN, 0);
  queue <int> q; q.emplace(S); d[S] = 0;
  while (!q.empty()) {
    int u = q.front(); q.pop(); vis[u] = 0;
    for (int i = head[u]; i; i = nex[i]) {
      int v = edge[i].nxt, w = edge[i].flow; ld c = edge[i].cost;
      if (w > 0 && d[v] > d[u] + c) {
        d[v] = d[u] + c;
        if (!vis[v])
          vis[v] = 1, q.emplace(v);
      }
    }
  } 
  return (d[T] < inf);
}

正确的代码：

const ld eps = 1E-7;
int cmp(ld x, ld y) {
  if (x - eps > y) return 1;
  if (x + eps < y) return -1;
  return 0;
}
bool spfa() {
  fill(d + 1, d + 1 + SN, INF);
  fill(vis + 1, vis + 1 + SN, 0);
  queue <int> q; q.emplace(S); d[S] = 0;
  while (!q.empty()) {
    int u = q.front(); q.pop(); vis[u] = 0;
    for (int i = head[u]; i; i = nex[i]) {
      int v = edge[i].nxt, w = edge[i].flow; ld c = edge[i].cost;
      if (w > 0 && cmp(d[v], d[u] + c) == 1) {
        d[v] = d[u] + c;
        if (!vis[v])
          vis[v] = 1, q.emplace(v);
      }
    }
  }
  return (cmp(d[T], INF) == -1);
}