최소 연결 그래프의 최대 합을 찾는 C++ 프로그램

최소 연결 그래프가 있다고 가정해 보겠습니다. 즉, 간선을 삭제하면 그래프 연결이 끊어집니다. 그래프에는 n개의 정점이 있고 가장자리는 "edges" 배열에 제공됩니다. 또한 n개의 정수 값을 포함하는 "vertexValues" 배열을 얻습니다.

이제 다음을 수행합니다. -

• 각 꼭지점에 양의 정수를 쓴 다음 분수를 계산해 봅니다.

• 두 정점을 연결하는 가장자리가 있고 두 정점 중 더 작은 값을 가장자리에 둡니다.

• 모든 간선 값을 더하여 점수를 계산합니다.

정점에 값을 배치하여 얻을 수 있는 최대값을 찾아야 합니다. 총합의 최대값과 정점에 쓸 값을 출력해야 합니다.

따라서 입력이 n = 6과 같으면 Edges = {{1, 2}, {2, 3} , {2, 4}, {4, 5}, {3, 6}}, vertexValues ​​​​= { 1, 2, 3, 4, 5, 6} 그러면 출력은 15, 3 1 2 4 5 6이 됩니다. 주어진 방식으로 0에서 n – 1까지의 값을 넣을 수 있기 때문입니다. 3 1 2 4 정점에 5 6.

이 문제를 해결하기 위해 다음 단계를 따릅니다. -

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])

예제

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. -

#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;
}

Input

6, {{1, 2}, {2, 3}, {2, 4}, {4, 5}, {3, 6}}, {1, 2, 3, 4, 5, 6}

Output

15
3 1 2 4 5 6

위 내용은 최소 연결 그래프의 최대 합을 찾는 C++ 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!