题意：给定一个有向图，求边权平均值最小的环的边权平均值。
二分
若环平均值等于mid，则 w1+w2+⋯+wk≥mid⋅k，即 (w1−mid)+(w2−mid)+⋯+(wk−mid)≥0，即没有负环，所以如果有负环，则表明该环平均值小于mid。
用Bellman判负环即可。
注意有负环和有负权边是不同的！
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 110;
const double eps = 1e-5;
int T, n, m;
struct edge
{
int from, to, dist;
};
struct Bellman
{
int n, m;
vector<edge>edges;
vector<int>G[maxn];
bool inq[maxn];
double d[maxn];
int p[maxn], cnt[maxn];
void init(int n) {
this->n = n;
for (int i = 1; i <= n; i++)G[i].clear();
edges.clear();
}
void add_edge(int u, int v, int dist) {
edges.push_back(edge{ u,v,dist });
m = edges.size();
G[u].push_back(m - 1);
}
bool negative(double ad) {
queue<int>Q;
memset(inq, 0, sizeof(inq));
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= n; i++) {
d[i] = 0;
inq[i] = true;
Q.push(i);
}
while (!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;
for (int i = 0; i < G[u].size(); i++) {
edge& e = edges[G[u][i]];
if (d[e.to] > d[u] + e.dist - ad) {
d[e.to] = d[u] + e.dist - ad;
p[e.to] = G[u][i];
if (!inq[e.to]) {
Q.push(e.to);
inq[e.to] = true;
if (++cnt[e.to] > n)return true;
}
}
}
}
return false;
}
};
Bellman bell;
int main() {
scanf("%d", &T);
for (int tt = 1; tt <= T; tt++) {
scanf("%d%d", &n, &m);
bell.init(n);
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
bell.add_edge(u, v, w);
}
double l = 0, r = 1e7 + 5;
while (r - l > eps) {
double mid = (l + r) / 2;
if (bell.negative(mid))r = mid;
else l = mid + eps;
}
printf("Case #%d: ", tt);
if (r == 1e7 + 5)printf("No cycle found.\n");
else {
printf("%.2f\n", l);
}
}
return 0;
}
|
