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