题解：UVA11090 Going in Cycle!!

· · 题解

可能更好的阅读体验

本题就是大名鼎鼎的最优比率环的问题。

我们不难注意到，平均值就是如下：

\overline{x}=\frac{\sum c_i}{cnt}

其中 cnt 代表点个数，而 c_{i} 代表权值和。

学过分数规划的想必已经秒了，没事我们一步一步推。

根据题意有：

\begin{aligned} ans & \rightarrow \frac{\sum c_i}{cnt} \ge \overline{x} \\ & =\sum c_i \ge \overline{x} \times cnt \\ & =\sum c_{i} - \overline{x} \times cnt \ge 0 \\ & = \sum (c_{i} - \overline{x}) \ge 0 \\ & = \sum (\overline{x}- c_{i}) \le 0 \end{aligned}

这是什么，负环？我们把边权改成 \overline{x}-c_{i} 不就是在让我们找一个环使得权值为负数，这不就是负环吗。

根据上面的不等式，我们不难看出我们需要二分这个 \overline{x}。我们用 SPFA 来判断负环，若有负环我们将 \overline{x} 调小，否则调大，这样就满足题意了。

接下来是代码时间，但是这里需要有几点注意：

  1. BFS 的 SPFA 会炸，请使用 DFS 版本的 SPFA，详情见代码。
  2. double 精度不够，请使用 long double。
  3. 时刻注意精度问题！
  4. 最后结果要输出 \dfrac{l+r}{2}，不然会被 hack 精度（没错 long double 还是不够）。

代码通过 uDebug 上所有 hack，同时讨论区内个人 hack 也通过，感谢 hack 提供者们的贡献。也欢迎来 hack 我代码 www。

#include<bits/stdc++.h>
#define double long double
using namespace std;
constexpr int MN=55;
constexpr double eps=1e-10;
struct Edge{
    int v;
    double w;
};
int n,m,tot;
double l,r,dis[MN];
bool vis[MN];
vector<Edge> adj[MN];

int cmp(double x,double y){
    if(fabs(x-y)<eps) return 0;
    if(x>y) return 1;
    return -1;
}

bool dfs(int u,double k){
    vis[u]=1;
    for(auto e:adj[u]){
        int v=e.v;
        auto w=e.w;
        if(dis[v]>dis[u]+w-k){
            dis[v]=dis[u]+w-k;
            if(vis[v]||dfs(v,k)){
                return vis[u]=0,1;
            }
        }
    }
    return vis[u]=0;
}

bool check(double k){
    memset(dis,0,sizeof(dis));
    for(int i=1;i<=n;i++){
        if(dfs(i,k)) return 1;
    }
    return 0;
}

void init(){
    for(int i=1;i<=n;i++) adj[i].clear(),vis[i]=0;
}

void solve(){
    init();
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        double w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
    }
    l=0,r=1e9;
    while(r-l>eps){
        double mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid;
    }
    if(cmp(l,1e9)==0) cout<<"No cycle found.\n";
    else cout<<fixed<<setprecision(2)<<(l+r)/2<<'\n';
}

int main(){
    int T;
    cin>>T;
    while(T--){
        cout<<"Case #"<<++tot<<": ";
        solve();
    }
    return 0;
}