题目大意
给定一个带权有向图，定义圈的平均值为一个有向圈上所有边权的平均值，求最小的平均值。数据保证连通、有圈、存在一个点从它开始能到达所有的点。
1⩽n⩽3,000
1⩽m⩽10,000
∣wi∣⩽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;
}
|