「Bzoj 1690」「Usaco2007 Dec」奶牛的旅行 (最优比率环)

BZOJ 1690
最优比率环模板，一条边的花费定为$f_{v}-x \times E_w$，其中$E=(u,v)，E_w$为边权
具体看这里

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1000 + 5, MAXM = 5000 + 5;
struct data {
    int v, wi;
    db p;
}ed[MAXM];
int n, m, en, fi[MAXN];
vector<int> G[MAXN];
int flag, vis[MAXN];
db dis[MAXN]; 
void spfa(int u) {
    if (flag) return ;
    vis[u] = true;
    for (int i = 0; i < G[u].size(); i++) {
        int v = ed[G[u][i]].v;
        db p = ed[G[u][i]].p;
        if (dis[u] + p > dis[v]) {
            dis[v] = dis[u] + p;
            if (vis[v]) {flag = true; return ;}
            spfa(v);
        }
    }
    vis[u] = false;
}
bool check() {
    flag = false;
    for (int i = 1; i <= n; i++) dis[i] = vis[i] = 0;
    for (int i = 1; i <= n; i++) {
        spfa(i);
        if (flag) return true;
    }
    return false;
}
void rebuild(double x) {
    for (int i = 1; i <= m; i++) ed[i].p = (db)fi[ed[i].v] - (db)ed[i].wi * x;
}
void ins(int u, int v, int c) {
    en++, ed[en] = (data){v, c, 0}, G[u].push_back(en);
}
void clean() {
    en = 0;
    for (int i = 0; i <= n; i++) G[i].clear();
}
void solve() {
    clean();
    int totc = 0;
    for (int i = 1; i <= n; i++) scanf("%d", &fi[i]);
    for (int i = 1; i <= m; i++) {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        ins(u, v, c), totc += c;
    }
    double l = 0.0, r = (db)totc + 1.0;
    for (int i = 1; i <= 100; i++) {
        double mid = (l + r) / 2.0;
        rebuild(mid);
        if (check()) l = mid; else r = mid;
    }
    printf("%.2f\n", l);
}
int main() {
    scanf("%d%d", &n, &m), solve();
    return 0;
}