[BZOJ 1486][HNOI 2009] 最小圈

发表于

题目大意

给定一个带权有向图，定义圈的平均值为一个有向圈上所有边权的平均值，求最小的平均值。数据保证连通、有圈、存在一个点从它开始能到达所有的点。

\(1\leqslant n \leqslant 3,000\)

\(1 \leqslant m \leqslant 10,000\)

\(|w_i| \leqslant 10,000,000\)

题目链接

BZOJ 1486

题解

二分 + dfs 判断。

对于一个有向圈，如果我们减去其平均值（再略大一点），它会成为一个负环，于是我们二分减去的值。判断时，从每个点开始用 dfs 并记录距离，像最短路一样更新（据说是叫「dfs 版的 spfa」），发现负环时返回。

代码

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
#include <cstdio>
#include <algorithm>
#include <new>
const int MAXN = 3005;
const int MAXM = 10005;
const double MAXW = 10000005;
struct Edge;
struct Node {
    Edge *e;
    double dist;
    bool vis;
} N[MAXN];
struct Edge {
    Node *u, *v;
    Edge *next;
    double w;
    Edge() {}
    Edge(Node *u, Node *v, double w) : u(u), v(v), w(w), next(u->e) {}
} _pool[MAXM], *_cur = _pool;
void addEdge(int u, int v, double w) {
    N[u].e = new (_cur++) Edge(&N[u], &N[v], w);
}
bool dfs(Node *u) {
    u->vis = true;
    for (Edge *e = u->e; e; e = e->next) {
        if (e->v->dist > u->dist + e->w) {
            if (e->v->vis) return true;
            e->v->dist = u->dist + e->w;
            if (dfs(e->v)) return true;
        }
    }
    u->vis = false;
    return false;
}
int n;
bool check(double x) {
    for (Edge *e = _pool; e != _cur; e++) e->w -= x;
    for (int i = 1; i <= n; i++) N[i].vis = false, N[i].dist = 0;
    bool flag = false;
    for (int i = 1; i <= n; i++) if (!flag && dfs(&N[i])) flag = true;
    for (Edge *e = _pool; e != _cur; e++) e->w += x;
    return flag;
}
double dichotomy() {
    double l = -MAXW, r = MAXW;
    int lambda = 60;
    while (lambda--) {
        double mid = l + (r - l) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}
int main() {
    int m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v;
        double w;
        scanf("%d %d %lf", &u, &v, &w);
        addEdge(u, v, w);
    }
    printf("%.8lf\n", dichotomy());
    return 0;
}