洛谷P3199 [HNOI2009]最小圈

十一月 05, 2020 3598

题意简述

给定一张有向带边权图，求出所有环的边权平均值最小是多少。保留 8 位小数。

解题思路

一年之前写过的题了。今天又考了原题结果没想出来，于是来补一发题解。

考虑二分。我们二分一个 d 表示最小的边权平均值，check 的时候每次把所有边的边权都减掉 d 然后判断是否存在负环即可，如果存在负环就说明答案合法。

为什么是对的？

假定我们有一个含 k 条边的环，在减法之后环长（边权之和）恰好为零甚至是负数。这意味着什么？

\begin{aligned} &\sum_{i = 1}^k (w_i - d) \leq 0 \\&\Leftrightarrow\sum_{i = 1}^k w_i - \sum_{i = 1}^k d \leq 0 \\&\Leftrightarrow\sum_{i = 1}^k w_i \leq d\cdot k \\&\Leftrightarrow\frac{1}{k}\sum_{i = 1}^k w_i \leq d \\&\Leftrightarrow\mathrm{answer} \leq d \end{aligned}

所以我们二分出来的 d 确实是答案没问题。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <queue>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define rap(a,s,t,i) for (int a = s; a <= t; a += i)
#define basketball(a,t,s,i) for (int a = t; a > s; a -= i)
#define countdown(s) while (s --> 0)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

typedef long long int lli;

int getint() { int x; scanf("%d", &x); return x; }
lli getll() { long long int x; scanf("%lld", &x); return x; }

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

struct Edge {
    int v;
    double w;
    
    Edge(int v = 0, double w = 0.0) : v(v), w(w) {}
};

std::vector<Edge> head[MAXN];

int n, m;
double dis[MAXN];
bool inQueue[MAXN], negLoop;

inline void addEdge(int u, int v, double w) { head[u].push_back(Edge(v, w)); }
inline void Modify(double w) {
    for (int i = 1; i <= n; ++i) {
        for (int k = 0, siz = (int) head[i].size(); k < siz; ++k) {
            head[i][k].w += w;
        }
    }
}

void SPFA_NegativeLoop(int st) {
    // dfs 求负环
    inQueue[st] = true;
    if (negLoop) return;
    for (int i = 0, siz = (int) head[st].size(); i < siz; ++i) {
        int next = head[st][i].v;
        if (dis[next] > dis[st] + head[st][i].w) {
            if (inQueue[next]) { return (void) (negLoop = true); }
            dis[next] = dis[st] + head[st][i].w;
            SPFA_NegativeLoop(next);
        }
    }
    inQueue[st] = false;
}

bool Check(double mid) {
    memset(dis, 0, sizeof dis);
    memset(inQueue, false, sizeof inQueue);
    negLoop = false;
    Modify(-mid);
    for (int i = 1; i <= n; ++i) {
        SPFA_NegativeLoop(i);
        if (negLoop) break;
    }
    Modify(mid);
    return negLoop;
}

int main() {
    n = getint(); m = getint();
    double l = INT_MAX, r = 0;
    rap (i, 1, m, 1) {
        int u = getint(), v = getint();
        double w = 0.0;
        scanf("%lf", &w);
        addEdge(u, v, w);
        l = std::min(w, l);
        r = std::max(w, r);
    }
    double ans = 0;
    while (l - r < eps) {
        double mid = (l + r) / 2;
        if (Check(mid)) {
            r = mid - eps;
            ans = r;
        } else l = mid + eps;
    }
    printf("%0.8lf", ans);
    return 0;
}