「EC Final 2020」D. City Brain

「题意」

给定一个 $n$ 个点 $m$ 条边的无向图,初始边权都是 $1$,给定两组起点和终点 $(s_1,t_1)$ 和 $(s_2,t_2)$ 。

现在有 $k$ 次机会,每次可以令某条边的边权 $+1$。通过一条边的时间为其边权的倒数,求 $\min{dis(s_1,t_1)+dis(s_2,t_2)}$。

$n,m\leq 5000, k\leq 10^9$

「题目链接」

D - City Brain

「分析」

$(s_1,t_1)$ 和 $(s_2,t_2)$ 的两条路径可能存在交集,而修改交集上的边权会同时影响两条路径的时间,修改非交集的边则只会影响某一条路径的时间。

由于二者的贡献不同,我们要分开考虑。

鉴于原图是个很小的无权图,我们可以做 $n$ 次BFS, $O(nm)$ 求出任意两点间的最短距离。

然后可以枚举两路径相交部分的起点和终点,用 $O(n^2)$ 的复杂度算出两路径相交部分的长度为 $0\sim n-1$ 时,不相交部分的最短长度。

现在考虑,当相交路径和不相交路径的长度确定时,如何分配这 $k$ 次操作会使得答案最优。

假设两路径相交部分的长度为 $a$,不相交部分的长度为 $b$,将 $x$ 次操作分配给相交部分,则 $k-x$ 次操作分配给不相交部分。

显然平均分配给每条边会使得答案最优,最终的答案为
$$
f_{k,a,b}(x)=\frac{x\bmod a}{2 + \lfloor{\frac{x}{a}}\rfloor}+\frac{a-x\bmod a}{1 + \lfloor{\frac{x}{a}}\rfloor}+\frac{(k-x)\bmod b}{2 + \lfloor{\frac{k-x}{b}}\rfloor}+\frac{b-(k-x)\bmod b}{1 + \lfloor{\frac{k-x}{b}}\rfloor}
$$
这是个凸函数,因此可以用三分的方法取出它的最小值。

$a$ 只有 $0\sim n-1$ 这 $n$ 种情况,对于每个 $a$ 都预处理出了最小的 $b$ ,因此可以对于每个 $(a,b)$ 都求出它对应的最小值,答案就是所有情况的最小值。

复杂度 $O(nm+n\log{k})$。

「参考代码」

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
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define fir first
#define sec second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)x.size()
#define up(i, l, r) for (int i = l; i <= r; ++i)
#define dn(i, l, r) for (int i = l; i >= r; --i)
#define Trav(i, x) for (auto & i : x)
#define pb push_back
template<class T, class G> bool chkMax(T &x, G y) {
return y > x ? x = y, 1 : 0;
}
template<class T, class G> bool chkMin(T &x, G y) {
return y < x ? x = y, 1 : 0;
}

const int N = 5000 + 5;

int n, m, k;
int s1, t1, s2, t2;
int Mn[N];
int Dis[N][N];
vi g[N];

void bfs(int s, int Dis[]) {
queue<int> q;
q.push(s);
Dis[s] = 0;
while (!q.empty()) {
int x = q.front(); q.pop();
Trav(v, g[x]) {
if (chkMin(Dis[v], Dis[x] + 1)) {
q.push(v);
}
}
}
}

double cal(int num, int total) {
if (!num) return 0;
return 1.0 * (total % num) / (2 + total / num) + 1.0 * (num - total % num) / (1 + total / num);
}

double f(int a, int b, int p) {
return 2 * cal(a, p) + cal(b, k - p);
}

double get(int a, int b) {
int l = 0, r = k;
double lans = 0, rans = 0;
while (l < r) {
int lmid = l + (r - l) / 3;
int rmid = r - (r - l) / 3;
lans = f(a, b, lmid), rans = f(a, b, rmid);
if (lans <= rans) r = rmid - 1;
else l = lmid + 1;
}
return min(lans, rans);
}

void solve() {
cin >> n >> m >> k;
for (int i = 1; i <= n; ++i) g[i].clear();
for (int i = 1, u, v; i <= m; ++i) {
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
cin >> s1 >> t1 >> s2 >> t2;
memset(Dis, 0x3f, sizeof Dis);
for (int i = 1; i <= n; ++i) bfs(i, Dis[i]);
memset(Mn, 0x3f, sizeof Mn);
Mn[0] = Dis[s1][t1] + Dis[s2][t2];
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
if (Dis[i][j] > n) continue;
int d1 = Dis[i][s1] + Dis[j][t1];
int d2 = Dis[i][t1] + Dis[j][s1];
int d3 = Dis[i][s2] + Dis[j][t2];
int d4 = Dis[i][t2] + Dis[j][s2];
if (d1 > n && d2 > n) continue;
if (d3 > n && d4 > n) continue;
chkMin(Mn[Dis[i][j]], min(d1, d2) + min(d3, d4));
}
}
double ans = 1e9;
for (int i = 0; i < n; ++i) {
chkMin(ans, get(i, Mn[i]));
}
cout << fixed << setprecision(10) << ans << endl;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}