分数规划 spfa [SCOI2014]方伯伯运椰子

https://www.luogu.org/problemnew/show/P3288

今天比赛被第二题续了 gg..
看到有一个分数 然后分数规划一下
然后就不知道怎么做了
正解好像挺简单的
根据流量守恒 所以消出来的是一个圈
建一个新图 边权为退流以及加流的费用
费用变小就判一个负圈就好了
注意加边的时候要判断是否可以退流
复杂度\(O(nm \log ans)\)

有时候O2可能会防止RE 所以说边数点数要分开算

#include<bits/stdc++.h>
#define fo(i, n) for(int i = 1; i <= (n); i ++)
#define out(x) cerr << #x << " = " << x << "\n"
#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); ++ it)
using namespace std;
// by piano
template<typename tp> inline void read(tp &x) {
  x = 0;char c = getchar(); bool f = 0;
for(; c < '0' || c > '9'; f |= (c == '-'), c = getchar());
for(; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
if(f) x = -x;
}
template<typename tp> inline void arr(tp *a, int n) {
for(int i = 1; i <= n; i ++)
    cout << a[i] << " ";
  puts("");
}
#define db double
const int N = 2333, M = 23333;
const db inf = 1e14;
const db eps = 1e-6;
struct P {
int u, v, a, b, c, d;
inline void in(void) {
    scanf("%d%d%d%d%d%d", &u, &v, &a, &b, &c, &d);
  }
}p[M];
int n, m;
struct E {
int nxt, to; db w;
  E(int _nxt = 0, int _to = 0, db _w = 0) {
    nxt = _nxt, to = _to, w = _w;
  }
}e[M << 1];
int head[N], e_cnt = 0;
db d[N];
int book[N], cnt[N], s, t;

inline void add(int u, int v, db w) {
if(fabs(w) < eps) return ;
  e[++ e_cnt] = E(head[u], v, w); head[u] = e_cnt;
}

inline void init(db now) {
  e_cnt = 0;
  memset(head, 0, sizeof head);
for(int i = 1; i <= m; i ++) if(p[i].u != s) {
    add(p[i].u, p[i].v, now + p[i].d + p[i].b);
if(p[i].c >= eps)
      add(p[i].v, p[i].u, now + p[i].a - p[i].d);
  }
}

inline int spfa(int s) {
for(int i = 0; i <= n + 2 + 2; i ++)
    d[i] = inf;
  memset(book, 0, sizeof book);
  memset(cnt, 0, sizeof cnt);
  queue<int> q;
  q.push(s); book[s] = 1; d[s] = 0;
while(!q.empty()) {
int u = q.front(); q.pop(); book[u] = 0;
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(d[v] > d[u] + e[i].w) {
        d[v] = d[u] + e[i].w;
if(!book[v]) {
          book[v] = 1;
          q.push(v);
if(++ cnt[v] > n + 2)
return 1;
        }
      }
    }
  }
return 0;
}

inline int check(db now) {
  init(now);
return spfa(1);
}

main(void) {
  read(n); read(m);
  s = n + 1; t = n + 2;
for(int i = 1; i <= m; i ++)
    p[i].in();
  db l = 0.0, r = 23333;
while(fabs(r - l) >= eps) {
    db mid = (l + r) / 2.0;
    check(mid) ? l = mid : r = mid;
  }
  printf("%.2f\n", l);
}