最小圈

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1609 字
二分答案加DFS版SPFA判负环
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1506
// 题意：给 n 点 m 条带实权有向边，求图中所有环的平均边权最小值，输出到小数点后 8 位。
// 思路：二分答案 mid，把边权改成 w - mid，若存在负环说明有环均值小于 mid，上界下压，否则抬下界。
// 1. 判负环用 DFS 版 SPFA，回溯栈上的点构成环时立刻返回，比普通队列 SPFA 快很多。
// 2. 所有点的 dis 初始化为 0 等价于加了一个指向所有点的虚拟源点，能判出全图的负环。
// 复杂度：O(log V * n * m) 时间 / O(n + m) 空间
// 易错点：边权是实数，读入要用 double，二分次数要够（60 次左右）才能保证 8 位小数。
// 易错点：退出 DFS 前必须把 instk 清掉，否则会把正常的跨子树边误判成环。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3005;
struct Edge{
    int to;
    double w;
};
vector<Edge> g[MAXN];
double dis[MAXN];
bool instk[MAXN];
int n, m;
bool dfs(int u, double mid){
    instk[u] = true;
    for(int i = 0; i < (int)g[u].size(); i++){
        int v = g[u][i].to;
        double w = g[u][i].w - mid;
        if(dis[v] > dis[u] + w){
            dis[v] = dis[u] + w;
            if(instk[v]) return true;
            if(dfs(v, mid)) return true;
        }
    }
    instk[u] = false;
    return false;
}
bool check(double mid){
    for(int i = 1; i <= n; i++){
        dis[i] = 0.0;
        instk[i] = false;
    }
    for(int i = 1; i <= n; i++){
        if(dfs(i, mid)) return true;
    }
    return false;
}
int main(){
    if(!(cin >> n >> m)) return 0;
    for(int i = 0; i < m; i++){
        int u, v;
        double w;
        cin >> u >> v >> w;
        Edge e;
        e.to = v;
        e.w = w;
        g[u].push_back(e);
    }
    double lo = -1e7;
    double hi = 1e7;
    for(int it = 0; it < 60; it++){
        double mid = (lo + hi) / 2.0;
        if(check(mid)) hi = mid;
        else lo = mid;
    }
    cout << fixed << setprecision(8) << lo << "\n";
    return 0;
}
最小圈

正文

一本通·提高篇的其它内容
