Giả sử, chúng ta được cho một đồ thị liên thông cực tiểu. Điều đó có nghĩa là loại bỏ bất kỳ cạnh nào sẽ làm cho đồ thị bị ngắt kết nối. Đồ thị có n đỉnh và các cạnh được cho trong một mảng 'cạnh'. Cũng có một mảng 'vertexValues' được cung cấp cho chúng tôi chứa n giá trị nguyên.
Bây giờ, chúng tôi làm như sau -
-
Chúng tôi viết một số nguyên dương trên mỗi đỉnh và sau đó thử tính điểm.
-
Có một cạnh nối hai đỉnh, ta đặt giá trị nhỏ hơn của hai đỉnh đó.
-
Chúng tôi tính điểm bằng cách cộng tất cả các giá trị cạnh.
Chúng ta phải tìm giá trị lớn nhất có thể đạt được bằng cách đặt các giá trị trên các đỉnh. Chúng ta phải in ra tổng giá trị lớn nhất và các giá trị được ghi trên các đỉnh.
Vì vậy, nếu đầu vào là n =6, các cạnh ={{1, 2}, {2, 3}, {2, 4}, {4, 5}, {3, 6}}, vertexValues ={1, 2, 3, 4, 5, 6}, thì kết quả sẽ là 15, 3 1 2 4 5 6, vì chúng ta có thể đặt các giá trị trên các đỉnh từ 0 đến n - 1 theo cách đã cho 3 1 2 4 5 6 .
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
N := 100
Define arrays seq and res of size N.
Define an array tp of size N.
ans := 0
Define a function dfs(), this will take p, q,
res[p] := seq[c]
if p is not equal to 0, then:
ans := ans + seq[c]
(decrease c by 1)
for each value x in tp[p], do:
if x is not equal to q, then:
dfs(x, p)
for initialize i := 0, when i + 1 < n, update (increase i by 1), do:
tmp := first value of edges[i]- 1
temp := second value of edges[i] - 1
insert temp at the end of tp[tmp]
insert tmp at the end of tp[temp]
for initialize i := 0, when i < n, update (increase i by 1), do:
seq[i] := vertexValues[i]
c := n - 1
sort the array seq
dfs(0, 0)
print(ans)
for initialize i := n - 1, when i >= 0, update (decrease i by 1), do:
print(res[i]) Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
#define N 100
int seq[N], res[N];
vector<int> tp[N];
int ans = 0, c;
void dfs(int p, int q) {
res[p] = seq[c];
if(p != 0)
ans += seq[c];
c--;
for(auto x : tp[p]) {
if(x != q)
dfs(x, p);
}
}
void solve(int n, vector<pair<int,int>> edges, int vertexValues[]){
for(int i = 0; i + 1 < n; i++) {
int tmp = edges[i].first - 1;
int temp = edges[i].second - 1;
tp[tmp].push_back(temp);
tp[temp].push_back(tmp);
}
for(int i = 0; i < n; i++)
seq[i] = vertexValues[i];
c = n - 1;
sort(seq, seq + n);
dfs(0, 0);
cout << ans << endl;
for(int i = n - 1; i >= 0; i--)
cout << res[i] << " ";
cout << endl;
}
int main() {
int n = 6;
vector<pair<int,int>> edges = {{1, 2}, {2, 3}, {2, 4}, {4, 5},{3, 6}};
int vertexValues[] = {1, 2, 3, 4, 5, 6};
solve(n, edges, vertexValues);
return 0;
} Đầu vào
6, {{1, 2}, {2, 3}, {2, 4}, {4, 5}, {3, 6}}, {1, 2, 3, 4, 5, 6}
Đầu ra
15 3 1 2 4 5 6