题目描述

考虑带权的有向图 G=(V,E) 以及 w:E→R，每条边 e=(i,j)(i≠j,i∈V,j∈V) 的权值定义为 wi,j，令 n=|V|。

c=(c1,c2,⋯,ck)(ci∈V)是 G 中的一个圈当且仅当 (ci,ci+1)(1≤i<k) 和 (ck,c1) 都在 E 中，这时称 k 为圈 c 的长度。

同时令 ck+1=c1，并定义圈 c=(c1,c2,⋯,ck) 的平均值为：μ(c)=1k∑i=1kwci,ci+1
即 c 上所有边的权值的平均值。

令 μ∗(c)=min{μ(c)} 为 G 中所有圈 c 的平均值的最小值。

现在的目标是：在给定了一个图 G=(V,E) 以及 w:E→R 之后，请求出 G 中所有圈 c 的平均值的最小值 μ∗(c)=min{μ(c)}。

输入样例

4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3

输出样例

3.66666667

解析

    如果刚拿到这道题,也许会二分平均值,然后暴力找环,但是不仅会超时,实现也比较困难

但是我们可以从二分下手,因为二分总权值是mid*num(环上点的数量),如果我环上的总权值

小于它就可以了,即

mid*num>sum(val[i]) ==> (mid+mid+...)>sum(val[i])

    我们同时减去mid,发现就是再减mid上判断是否出现负环

C++ 代码

//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")

/*
    二分,然后减去mid,判断

是否出现负环 
*/
#include<bits/stdc++.h>

#define R register
#define ll long long
#define inf INT_MAX
#define dl double

using namespace std;

const int N=3e3+10,M=1e4+10;
const dl eps=1e-9;

int n,m,tot;
dl val[M],f[N];
int h[N],nex[M],ver[M],vis[N];

inline void add(int x,int y,dl z)
{
    nex[tot]=h[x];
    ver[tot]=y;
    val[tot]=z;
    h[x]=tot++;
}

inline bool dfs(int u,dl mid)
{
    vis[u]=1;
    for (int i=h[u];~i;i=nex[i])
    {
        int j=ver[i];
        if(f[j]>f[u]+val[i]-mid)
        {
            f[j]=f[u]+val[i]-mid;
            if(vis[j]) return 1;
            else if(dfs(j,mid)) return 1;
        }
    }

    vis[u]=0;
    return 0;
}

inline bool check(dl mid)
{
    memset(vis,0,sizeof(vis));
    memset(f,0,sizeof(f));
    for (int i=1;i<=n;i++)
        if(dfs(i,mid)) return 1;

    return 0;
}

int main()
{
    memset(h,-1,sizeof(h));

    dl l=1e8,r=-1e7;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int x,y;dl z;
        scanf("%d%d%lf",&x,&y,&z);
        add(x,y,z);
        l=min(l,z);r=max(r,z);
    }

    while(r-l>eps)
    {
        dl mid=(l+r)/2.0;
        if(check(mid)) r=mid;
        else l=mid;
    }

    printf("%.8lf\n",l);

    return 0;
}