UVA

题意：求有向图平均值最小环

看到平均值就想到分数规划问题，解法是二分答案，假设存在一个平均值小于等于x的环，那么把每条边的权值减去x，然后判断是否存在负环即可。Floyed就可以判负环，spfa也行

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N=100+10,inf=0x3f3f3f3f;
int n,m,ka;
db g[N][N],buf[N][N];
bool ok(db x) {
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            g[i][j]=buf[i][j]-x;
    for(int k=1; k<=n; ++k)
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=n; ++j)
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
    for(int i=1; i<=n; ++i)if(g[i][i]<=0)return 1;
    return 0;
}
db bi(db l,db r) {
    for(int i=0; i<50; ++i) {
        db mid=(l+r)/2;
        ok(mid)?r=mid:l=mid;
    }
    return l;
}

int main() {
    int _;
    for(scanf("%d",&_); _--;) {
        printf("Case #%d: ",++ka);
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; ++i)for(int j=1; j<=n; ++j)g[i][j]=inf;
        while(m--) {
            int u,v;
            db c;
            scanf("%d%d%lf",&u,&v,&c);
            g[u][v]=min(g[u][v],c);
        }
        for(int i=1; i<=n; ++i)for(int j=1; j<=n; ++j)buf[i][j]=g[i][j];
        db ans=bi(0,inf);
        if(ans>1e8)puts("No cycle found.");
        else printf("%.2f
",ans);
    }
    return 0;
}