Program C++ untuk mencari jumlah maksimum graf yang disambungkan secara minimum

Andaikan kita mempunyai graf bersambung minima. Ini bermakna pemadaman mana-mana tepi akan memutuskan sambungan graf. Graf mempunyai n bucu dan tepi diberikan dalam tatasusunan "tepi". Kami juga mendapat tatasusunan "vertexValues" yang mengandungi n nilai integer.

Sekarang, kami melakukan perkara berikut -

• Kami menulis integer positif pada setiap bucu dan kemudian cuba mengira pecahan.

• Terdapat tepi yang menghubungkan dua bucu dan kami meletakkan nilai yang lebih kecil daripada dua bucu di tepi.

• Kami mengira markah dengan menambah semua nilai tepi.

Kita perlu mencari nilai maksimum yang boleh dicapai dengan meletakkan nilai pada bucu. Kita perlu mencetak jumlah nilai maksimum dan nilai yang akan ditulis ke puncak.

Jadi jika input adalah seperti n = 6, maka Edges = {{1, 2}, {2, 3} , {2, 4}, {4, 5}, {3, 6}}, vertexValues ​​​= { 1, 2, 3, 4, 5, 6} maka keluarannya ialah 15, 3 1 2 4 5 6 kerana kita boleh meletakkan nilai dari 0 hingga n – 1 dengan cara yang diberikan 3 1 2 4 5 6 pada puncak.

Untuk menyelesaikan masalah ini kami akan mengikuti langkah berikut -

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

Contoh

Mari kita lihat pelaksanaan berikut untuk pemahaman yang lebih baik -

#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

Atas ialah kandungan terperinci Program C++ untuk mencari jumlah maksimum graf yang disambungkan secara minimum. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!