CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Vacation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int n, l[N], s[N], v[N];
int main()
{
while (~scanf("%d", &n))
{
for (int i = 0; i <= n; ++i)
scanf("%d", &l[i]);
for (int i = 0; i <= n; ++i)
scanf("%d", &s[i]);
for (int i = 0; i <= n; ++i)
scanf("%d", &v[i]);
double ans = s[0] * 1.0 / v[0], sum = 0;
for (int i = 1; i <= n; ++i)
sum += l[i], ans = max(ans, (sum + s[i]) / v[i]);
printf("%.9f\n", ans);
}
}
Path
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 4e18;
struct Graph
{
struct Vertex
{
vector<int> o;
};
struct Edge
{
int first, second;
ll len, cap;
};
vector<Vertex> v;
vector<Edge> e;
Graph(int n) : v(n) {}
void add(const Edge &ed)
{
v[ed.first].o.push_back(e.size());
e.push_back(ed);
}
};
struct Dijkstra : Graph
{
vector<ll> d;
Dijkstra(int n) : Graph(n) {}
void ask(int s)
{
d.assign(v.size(), INF);
priority_queue<pair<ll, int>> q;
for (q.push(make_pair(d[s] = 0, s)); !q.empty();)
{
ll dis = -q.top().first;
int u = q.top().second;
if (q.pop(), d[u] < dis)
continue;
for (int i = 0, k, to; i != v[u].o.size(); ++i)
if (k = v[u].o[i], to = e[k].second,
d[to] > d[u] + e[k].len)
{
d[to] = d[u] + e[k].len;
q.push(make_pair(-d[to], to));
}
}
}
};
struct ISAP : Graph
{
ll flow;
vector<ll> f;
vector<int> h, cur, gap;
ISAP(int n) : Graph(n) {}
void add(Edge ed)
{
Graph::add(ed);
swap(ed.first, ed.second), ed.cap = 0;
Graph::add(ed);
}
ll dfs(int s, int u, int t, ll r)
{
if (r == 0 || u == t)
return r;
ll _f, _r = 0;
for (int &i = cur[u], k; i < v[u].o.size(); ++i)
if (k = v[u].o[i], h[u] == h[e[k].second] + 1)
{
_f = dfs(s, e[k].second, t, min(r - _r, e[k].cap - f[k]));
f[k] += _f, f[k ^ 1] -= _f, _r += _f;
if (_r == r || h[s] >= v.size())
return _r;
}
if (!--gap[h[u]])
h[s] = v.size();
return ++gap[++h[u]], cur[u] = 0, _r;
}
void ask(int s, int t)
{
h.assign(v.size(), 0);
cur.assign(v.size(), 0);
gap.assign(v.size() + 2, 0);
for (f.assign(e.size(), flow = 0); h[s] < v.size();)
flow += dfs(s, s, t, INF);
}
};
int main()
{
int t, n, m;
for (scanf("%d", &t); t--;)
{
scanf("%d%d", &n, &m);
Dijkstra g(n);
for (int i = 0, x, y, c; i < m; ++i)
{
scanf("%d%d%d", &x, &y, &c);
g.add({x - 1, y - 1, c, c});
}
g.ask(0);
ISAP h(n);
for (int i = 0; i < m; ++i)
if (g.d[g.e[i].first] + g.e[i].len == g.d[g.e[i].second])
h.add(g.e[i]);
h.ask(0, n - 1);
cout << h.flow << '\n';
}
}