Luogu

BZOJ

分析

这题感觉很Easy呀qwq

如果你做题做得多就会知道，平均数的题一般可以减去某个值，然后变为判负数。

对于这个题，二分答案$mid$，并将每条边的权值减去$mid$，然后就变成了$\mathrm{SPFA}$判负环。

具体来说，如果存在负环，则应该R=mid，否则应该L=mid。

然而这题用BFS的SPFA氵不过，用DFS的SPFA就能过了。

复杂度感觉有点假qwq

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

const int MAXN=3000+10;
const int MAXM=10000+10;
const double EPS=1e-9;

int n,m;

struct Edge { int v,nxt; double w; };
Edge e[MAXM];
int head[MAXN];

inline void addEdge(int u,int v,double w) {
    static int cnt=0;
    e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;
}

double dis[MAXN];
int vis[MAXN];

inline int SPFA(int u,double mid) {
    vis[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; double w=e[i].w-mid;
        if (dis[u]+w<dis[v]) {
            dis[v]=dis[u]+w;
            if (vis[v]||SPFA(v,mid)) return 1;
        }
    }
    vis[u]=0; return 0;
}

inline int check(double mid) { //存在负环返回true
    for (re int i=1;i<=n;++i) dis[i]=0,vis[i]=0;
    for (re int i=1;i<=n;++i)
        if (SPFA(i,mid)) return 1;
    return 0;
}

int main() {
    scanf("%d%d",&n,&m);
    for (re int i=1;i<=m;++i) {
        int u,v; double w;
        scanf("%d%d%lf",&u,&v,&w);
        addEdge(u,v,w);
    }
    double L=-1e7,R=1e7;
    while (R-L>EPS) {
        double mid=(L+R)/2;
        if (check(mid)) R=mid;
        else L=mid;
    }
    printf("%.8f\n",L);
    return 0;
}