C F 715 B − C o m p l e t e T h e G r a p h \mathrm{CF715B - Complete\ The\ Graph} CF715B−Complete The Graph
D e s c r i p t i o n \mathrm{Description} Description
给定一张 n n n 个点， m m m 条边的无向图，点的编号为 0 ∼ n − 1 0\sim n-1 0∼n−1，对于每条边权为 0 0 0 的边赋一个不超过 1 0 18 10^{18} 1018 的正整数权值，使得 S S S 到 T T T 的最短路长度为 L L L。
S o l u t i o n \mathrm{Solution} Solution
W a y 1 \mathrm{Way\ 1} Way 1
考虑将每 1 1 1 条长度为 0 0 0 的边记录出来，初始将其全部设置为 1 1 1（因为要求边权值 ∈ [ 1 , 1 0 18 ] \in[1,10^{18}] ∈[1,1018]），如果将这些边依次不断地加 1 1 1，则 S S S 到 T T T 的最短路的长度会不断地增加或不变，总之最短路长度是单调不降的。那么，如果有解就必定会找到一种方案，反之则不会。
观察数据范围可知，最多每条边会加到 L L L，有 m m m 条边，那么时间应为 O ( m 2 L log n ) O(m^2L\log n) O(m2Llogn)，因为还需加入 Dijkstra 的时间复杂度。
显然，会 TLE。不过，上文已分析最短路的长度是单调不降的，所以满足二分的性质，可以二分总共加 1 1 1 的个数，然后对于每跳边先加 ⌊ 个数 边数 ⌋ \lfloor\frac{个数}{边数}\rfloor ⌊边数个数⌋，之后对于 1 ∼ 个数 m o d 边数 1\sim 个数\bmod 边数 1∼个数mod边数 的边再加 1 1 1 即可。
时间复杂度： O ( m log L log n ) O(m\log L\log n) O(mlogLlogn)
C o d e Code Code
#include <bits/stdc++.h>
#define int long long
using 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;
}
else
cout << "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;
}
W a y 2 \mathrm{Way\ 2} Way 2
从 S S S 开始先做 1 1 1 遍 Dijkstra，记当前 L L L 与 S S S 到 T T T 的最短路的差值为 D i f f Diff Diff（即 D i f f = L − D 1 , T Diff=L-D_{1,T} Diff=L−D1,T）
之后再做第 2 2 2 遍 Dijkstra 的时候，当点 u u u 更新至点 v v v 时且当前边为特殊边（初始变为 0 0 0），若 D 2 , u + w i < D 1 , v + D i f f D_{2,u}+w_i< D_{1,v}+Diff D2,u+wi<D1,v+Diff，则说明这时候最短路长度少了，尽量要让其补上这缺失的部分，即 w i = D 1 , u + D i f f − D 2 , u w_i = D_{1,u}+Diff-D_{2,u} wi=D1,u+Diff−D2,u。修改后，再进行正常 Dijkstra 的更新即可。文章来源：https://www.toymoban.com/news/detail-827351.html
注：
D
1
,
i
D_{1,i}
D1,i 表示第
1
1
1 次 Dijkstra 到达
i
i
i 号点的最短路长度，
D
2
,
i
D_{2,i}
D2,i 表示第
2
2
2 次 Dijkstra 到达第
i
i
i 号点的最短路长度。文章来源地址https://www.toymoban.com/news/detail-827351.html
C o d e Code Code
#include <bits/stdc++.h>
#define int long long
using 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;
}
到了这里，关于【图论经典题目讲解】CF715B - Complete The Graph的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![FATAL Error: Unable to complete saved object migrations for the [.kibana_task_manager] index. Plea](https://imgs.yssmx.com/Uploads/2024/02/524710-1.png)
