【图论经典题目讲解】CF715B - Complete The Graph

$CF715B-\mathrm{Complete}\mathrm{The}\mathrm{Graph}$

$\mathrm{Description}$

给定一张 $n$ 个点，$m$ 条边的无向图，点的编号为 $0\sim n-1$，对于每条边权为 $0$ 的边赋一个不超过 $10^{18}$ 的正整数权值，使得 $S$ 到 $T$ 的最短路长度为 $L$。

$\mathrm{Solution}$

$\mathrm{Way}1$

考虑将每 $1$ 条长度为 $0$ 的边记录出来，初始将其全部设置为 $1$（因为要求边权值 $\in [1,10^{18}]$），如果将这些边依次不断地加 $1$，则 $S$ 到 $T$ 的最短路的长度会不断地增加或不变，总之最短路长度是单调不降的。那么，如果有解就必定会找到一种方案，反之则不会。

观察数据范围可知，最多每条边会加到 $L$，有 $m$ 条边，那么时间应为 $O(m^{2}L\log n)$，因为还需加入 Dijkstra 的时间复杂度。

显然，会 TLE。不过，上文已分析最短路的长度是单调不降的，所以满足二分的性质，可以二分总共加 $1$ 的个数，然后对于每跳边先加 $\lfloor \frac{个数}{边数}\rfloor$，之后对于 $1\sim 个数\mathrm{mod}边数$ 的边再加 $1$ 即可。

时间复杂度：$O(m\log L\log n)$

$Code$

#include <bits/stdc++.h>
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;const int SIZE = 2e4 + 10;int N, M, L, S, T;
int h[SIZE], e[SIZE], ne[SIZE], w[SIZE], idx;
std::vector<int> Id;
int Dist[SIZE], Vis[SIZE];void add(int a, int b, int c)
{e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}int Dijkstra()
{priority_queue<PII, vector<PII>, greater<PII>> Heap;memset(Dist, 0x3f, sizeof Dist);memset(Vis, 0, sizeof Vis);Dist[S] = 0, Heap.push({0, S});while (Heap.size()){auto Tmp = Heap.top();Heap.pop();int u = Tmp.second;if (Vis[u]) continue;Vis[u] = 1;for (int i = h[u]; ~i; i = ne[i]){int j = e[i];if (Dist[j] > Dist[u] + w[i]){Dist[j] = Dist[u] + w[i];Heap.push({Dist[j], j});}}}return Dist[T];
}int Check(int X)
{for (auto c : Id)w[c] = X / (int)(Id.size() / 2);for (int i = 0; i < (X % (int)(Id.size() / 2)) * 2; i += 2)w[Id[i]] += 1, w[Id[i] ^ 1] += 1;return Dijkstra();
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);memset(h, -1, sizeof h);cin >> N >> M >> L >> S >> T;int u, v, c, Cpy = M;while (M --){cin >> u >> v >> c;if (c) add(u, v, c), add(v, u, c);else{Id.push_back(idx), add(u, v, 1);Id.push_back(idx), add(v, u, 1);}}M = Cpy;if (!Id.size()){if (Dijkstra() == L){cout << "YES" << endl;for (int i = 0; i < idx; i += 2)cout << e[i ^ 1] << " " << e[i] << " " << w[i] << endl;}elsecout << "NO" << endl;return 0;}int l = Id.size() / 2, r = L * M;while (l < r){int mid = l + r >> 1;if (Check(mid) >= L) r = mid;else l = mid + 1;}if (Check(r) != L){cout << "NO" << endl;return 0;}cout << "YES" << endl;for (int i = 0; i < idx; i += 2)cout << e[i ^ 1] << " " << e[i] << " " << w[i] << endl;return 0;
}

$\mathrm{Way}2$

从 $S$ 开始先做 $1$ 遍 Dijkstra，记当前 $L$ 与 $S$ 到 $T$ 的最短路的差值为 $Diff$（即 $Diff=L-D_{1,T}$）

之后再做第 $2$ 遍 Dijkstra 的时候，当点 $u$ 更新至点 $v$ 时且当前边为特殊边（初始变为 $0$），若 $D_{2,u}+w_i<D_{1,v}+Diff$，则说明这时候最短路长度少了，尽量要让其补上这缺失的部分，即 $w_i=D_{1,u}+Diff-D_{2,u}$。修改后，再进行正常 Dijkstra 的更新即可。

注：
$D_{1,i}$ 表示第 $1$ 次 Dijkstra 到达 $i$ 号点的最短路长度，$D_{2,i}$ 表示第 $2$ 次 Dijkstra 到达第 $i$ 号点的最短路长度。

$Code$

#include <bits/stdc++.h>
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;const int SIZE = 2e4 + 10;int N, M, L, S, T;
int h[SIZE], e[SIZE], ne[SIZE], w[SIZE], f[SIZE], idx;
int D[2][SIZE], Vis[SIZE];void add(int a, int b, int c)
{if (!c) f[idx] = 1;e[idx] = b, ne[idx] = h[a], w[idx] = max(1ll, c), h[a] = idx ++;
}void Dijkstra(int dist[], int Turn)
{for (int i = 0; i < N; i ++)dist[i] = 1e18, Vis[i] = 0;priority_queue<PII, vector<PII>, greater<PII>> Heap;Heap.push({0, S}), dist[S] = 0;while (Heap.size()){auto Tmp = Heap.top();Heap.pop();int u = Tmp.second;if (Vis[u]) continue;Vis[u] = 1;for (int i = h[u]; ~i; i = ne[i]){int j = e[i];if (Turn == 2 && f[i] && dist[u] + w[i] < D[0][j] + L - D[0][T])w[i] = w[i ^ 1] = D[0][j] + L - D[0][T] - dist[u];if (dist[j] > dist[u] + w[i]){dist[j] = dist[u] + w[i];Heap.push({dist[j], j});}}}
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);memset(h, -1, sizeof h);cin >> N >> M >> L >> S >> T;int u, v, c;while (M --){cin >> u >> v >> c;add(u, v, c), add(v, u, c);}Dijkstra(D[0], 1);if (L - D[0][T] < 0){cout << "NO" << endl;return 0;}Dijkstra(D[1], 2);if (D[1][T] != L){cout << "NO" << endl;return 0;}cout << "YES" << endl;for (int i = 0; i < idx; i += 2)cout << e[i ^ 1] << " " << e[i] << " " << w[i] << endl;return 0;
}