Bzoj 1690(最优比率环)

BZOJ 1690
最优比率环模板,一条边的花费定为$f_{v}-x \times E_w$,其中$E=(u,v),E_w$为边权
具体看这里

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1000 + 5, MAXM = 5000 + 5;
struct data {
int v, wi;
db p;
}ed[MAXM];
int n, m, en, fi[MAXN];
vector<int> G[MAXN];
int flag, vis[MAXN];
db dis[MAXN];
void spfa(int u) {
if (flag) return ;
vis[u] = true;
for (int i = 0; i < G[u].size(); i++) {
int v = ed[G[u][i]].v;
db p = ed[G[u][i]].p;
if (dis[u] + p > dis[v]) {
dis[v] = dis[u] + p;
if (vis[v]) {flag = true; return ;}
spfa(v);
}
}
vis[u] = false;
}
bool check() {
flag = false;
for (int i = 1; i <= n; i++) dis[i] = vis[i] = 0;
for (int i = 1; i <= n; i++) {
spfa(i);
if (flag) return true;
}
return false;
}
void rebuild(double x) {
for (int i = 1; i <= m; i++) ed[i].p = (db)fi[ed[i].v] - (db)ed[i].wi * x;
}
void ins(int u, int v, int c) {
en++, ed[en] = (data){v, c, 0}, G[u].push_back(en);
}
void clean() {
en = 0;
for (int i = 0; i <= n; i++) G[i].clear();
}
void solve() {
clean();
int totc = 0;
for (int i = 1; i <= n; i++) scanf("%d", &fi[i]);
for (int i = 1; i <= m; i++) {
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
ins(u, v, c), totc += c;
}
double l = 0.0, r = (db)totc + 1.0;
for (int i = 1; i <= 100; i++) {
double mid = (l + r) / 2.0;
rebuild(mid);
if (check()) l = mid; else r = mid;
}
printf("%.2f\n", l);
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}
------ 本文结束 ------