Codeforces 716D 372-Div.2 Complete The Graph

Posted on Edited on In , ,

题目链接：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;
}