Codeforces 716D 372-Div.2 Complete The Graph

题目链接:Complete The Graph

题意:

给出一个无向图,每个边的权重都是正整数;现在有一些的边的权重丢失了,用0表示,需要给这些边补回正整数的权重,使得补充后,从起点S到终点T的最短路恰好等于L;给出任意一个补充的方案;如果无法构造出这样的图使得S到T的最短路等于L,输出NO。

题解:

用已知权重的边进行构图,丢失权重的边先不加入图中,分情况讨论

  • 求S到T的最短路,若最短路 < L,则问题无解,因为已经存在一条路 < L,新加入的边只会使最短路更短

  • 求S到T的最短路,若最短路 = L,将剩下的边权都赋值为一个无穷大值,这样就不会影响S到T的最短路,问题有解

  • 求S到T的最短路,若最短路 > L,则尝试把权重丢失的边添加到图中,试图缩小S到T的最短路:

    1. 由于最终所有边权重都必须是正整数,所以每条边的最小值是1;加入的每条边权重都是1时,是一种最优方案,最后计算S到T的最短路值一定是最小的
    2. 每加入一条权重1的边后,重新计算一次S到T最短路。
    3. 若加入当前边后,最短路 > L,则继续加入下一条
    4. 若所有边都加入图后,依然最短路 > L,则问题无解,因为这已经是最优方案
    5. 若加入当前边后,最短路 = L,说明当前边更新了S到T的最短路值,最短路必定包含当前边;将剩下的边都赋值为无穷大加入图中,就不会影响到S到T的最短路值
    6. 若加入当前边后,最短路 < L,说明当前边更新了S到T的最短路值,最短路必定包含当前边;delta = L - 最短路,把当前边的边权重变为 w = 1 + delta,那么最短路 = L,可知最短路依然必定包含该边,因为没加入该边时,最短路 > L;由于我们已经构造出了一个最短路 = L的方案,所有剩下的边,赋值为无穷大并加入图中即可

代码:

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <queue>
#include <iostream>

#define EDGE first
#define WEIGHT second
#define U first
#define V second

using namespace std;

typedef pair<int, int> pii;
const int MAXN = 1000;
const long long IINF = 10e17;

vector<pii> e[MAXN];
vector<pii> ept;
vector< pair<pii, int> > nept;
queue<int> que;
bool inq[MAXN];
long long d[MAXN];
int n, m, target, st, ed;

void spfa() {
for (int i = 0; i < n; i++) {
d[i] = i == st ? 0 : IINF;
inq[i] = i == st ? true : false;
}
que.push(st);

while (!que.empty()) {
int u = que.front();
que.pop();
inq[u] = false;

for (int i = 0; i < e[u].size(); i++) {
int v = e[u][i].first;
int w = e[u][i].second;

if (d[u] + w < d[v]) {
d[v] = d[u] + w;
if (!inq[v]) {
que.push(v);
inq[v] = true;
}
}
}
}
}

int main() {
while (scanf("%d%d%d%d%d", &n, &m, &target, &st, &ed) != EOF) {
for (int i = 0; i < n; i++)
e[i].clear();
ept.clear();
nept.clear();

for (int i = 0 ; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
if (w) {
e[u].push_back(make_pair(v, w));
e[v].push_back(make_pair(u, w));
nept.push_back(make_pair(make_pair(u, v), w));
} else {
ept.push_back(make_pair(u, v));
}
}

spfa();

if (d[ed] < target) {
puts("NO");
continue;
} else if (d[ed] == target) {
puts("YES");
for (int i = 0; i < nept.size(); i++) {
printf("%d %d %d\n",
nept[i].EDGE.U, nept[i].EDGE.V, nept[i].WEIGHT);
}
for (int i = 0; i < ept.size(); i++) {
printf("%d %d %lld\n", ept[i].first, ept[i].second, IINF);
}
continue;
}

int index = -1, weight = 0;
for (int i = 0; i < ept.size(); i++) {
int u = ept[i].first;
int v = ept[i].second;
e[u].push_back(make_pair(v, 1));
e[v].push_back(make_pair(u, 1));

spfa();

if (d[ed] <= target) {
index = i;
weight = 1 + target - d[ed];
break;
}
}
if (index == -1) {
puts("NO");
} else {
puts("YES");
for (int i = 0; i < nept.size(); i++) {
printf("%d %d %d\n",
nept[i].EDGE.U, nept[i].EDGE.V, nept[i].WEIGHT);
}
for (int i = 0; i < index; i++) {
printf("%d %d %d\n", ept[i].first, ept[i].second, 1);
}
printf("%d %d %d\n", ept[index].first, ept[index].second, weight);
for (int i = index + 1; i < ept.size(); i++) {
printf("%d %d %lld\n", ept[i].first, ept[i].second, IINF);
}
}
}
return 0;
}
坚持原创分享,您的支持将鼓励我继续创作!