题目链接

Solution [HNOI2009]最小圈

题目大意：给定一张有向图，求所有环的边权平均值中的最小值

\(0-1\)分数规划

分析：首先我们可以二分把这个问题转化成一个判定性问题

关键是怎么判断一个平均值为\(limit\)的环是否存在，我们发现，假定把所有边的边权统一减去\(limit\)后，如果有负环，说明至少存在一个平均值为\(limit\)的环，然后就可以二分了

交一发你会发现SPFA它NOIP了，于是我们要用\(dfs\)来判负环

我们初始把每个点的最短路置为\(0\)，从每个点开始（或者开一个虚拟点）跑\(dfs\)

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
typedef long double type;
const int maxn = 3333;
const type eps = 1e-10;
struct Edge{
    int to;
    type dist;
};
vector<Edge> G[maxn];
inline void addedge(int from,int to,type dist){G[from].push_back(Edge{to,dist});}
int n,m,u,v,flag,vis[maxn];
type w,l = 1e9,r = -1e9,dis[maxn],ans;
void spfa(int u,type delta){
    if(flag)return;
    vis[u] = 1;
    for(auto e : G[u])
        if(dis[u] + e.dist - delta < dis[e.to]){
            dis[e.to] = dis[u] + e.dist - delta;
            if(vis[e.to]){
                flag = true;
                break;
            }else spfa(e.to,delta);
        }
    vis[u] = 0;
}
inline bool check(type delta){
    for(int i = 1;i <= n;i++)dis[i] = vis[i] = 0;
    return flag = false,spfa(n + 1,delta),flag;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 1;i <= m;i++)
        cin >> u >> v >> w,addedge(u,v,w),l = min(l,w),r = max(r,w);
    for(int i = 1;i <= n;i++)addedge(n + 1,i,0),sort(G[i].begin(),G[i].end(),[](const Edge &a,const Edge &b){return a.dist < b.dist;});
    while(abs(l - r) > eps){
        type mid = (l + r) / 2;
        if(check(mid))ans = mid,r = mid - eps;
        else l = mid + eps;
    }
    cout << setiosflags(ios::fixed) << setprecision(8) << ans << '\n';
    return 0;
}

题解 P3199 【[HNOI2009]最小圈】

原文：https://www.cnblogs.com/colazcy/p/11826190.html