C++で解く最小連結グラフの最大合計スコアの求め方

問題の概要

「最小連結グラフ」とは、どの辺を1本でも取り除くとグラフが連結でなくなってしまう（分断されてしまう）グラフのことです。言い換えれば、このグラフは木構造と同じ性質を持ちます。

ここでは、n個の頂点を持つ最小連結グラフが与えられ、辺の情報は配列 edges として渡されます。あわせて、n個の整数値を格納した配列 vertexValues も与えられます。

次に、以下の操作を行います。

• 各頂点に正の整数を1つ書き込みます。
• 2つの頂点をつなぐ辺には、その両端の頂点に書かれた値のうち小さい方を記録します。
• すべての辺に書かれた値を合計したものを「スコア」とします。

目的は、頂点への値の割り当て方を工夫することで達成できるスコアの最大値を求めることです。最終的に、最大合計値と、そのとき各頂点に書くべき値を出力してください。

たとえば、入力が 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」になります。頂点にこの順で値を配置することで、合計15という最大スコアが達成できるためです。

解法のアプローチ

この問題は、貪欲法（グリーディ法）とDFS（深さ優先探索）を組み合わせることで効率的に解けます。

ポイントとなる考え方は次のとおりです。

• 辺の値は「両端のうち小さい方」で決まるため、大きな値ほど多くの辺に影響を与えられる場所（親側・根に近い位置）へ配置するのが有利です。
• そこで、値を昇順にソートし、根からDFSで頂点を訪問しながら、大きな値から順に割り当てていきます。

具体的な手順は以下のとおりです。

1. 辺リストをもとに隣接リストを作成する。
2. vertexValues を昇順にソートして配列 seq にコピーする。
3. 根（頂点0）からDFSを開始し、ソート済み配列の末尾（最大値）から順に値を割り当てる。
4. 根以外の頂点に割り当てられた値の総和が答え（最大スコア）になる。

アルゴリズム（擬似コード）

N := 100
サイズNの配列 seq と res を定義
サイズNの配列 tp を定義
ans := 0

関数 dfs(p, q):
    res[p] := seq[c]
    p が 0 でない場合:
        ans := ans + seq[c]
    c を 1 減らす
    tp[p] 内の各要素 x について:
        x が q と等しくない場合:
            dfs(x, p)

i := 0 から i + 1 < n の間（1ずつ増やす）:
    tmp := edges[i] の1番目の値 - 1
    temp := edges[i] の2番目の値 - 1
    tp[tmp] の末尾に temp を挿入
    tp[temp] の末尾に tmp を挿入

i := 0 から i < n の間（1ずつ増やす）:
    seq[i] := vertexValues[i]

c := n - 1
seq をソートする
dfs(0, 0)
ans を出力する
i := n - 1 から i >= 0 の間（1ずつ減らす）:
    res[i] を出力する

C++実装例

それでは、理解を深めるために実際の実装を見てみましょう。

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

入力

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

出力

15
3 1 2 4 5 6

計算量

隣接リストの構築とソート、およびDFSの走査により、全体の計算量は O(n log n) となります。頂点数が増えても効率よく動作する実装です。