【C++】グラフの連結性を保ちながら辺を削除し、スコアの最大削減量を求める方法

問題概要

n 個の頂点と m 本の辺からなる重み付き無向グラフを考えます。グラフの「スコア」は、含まれるすべての辺の重みの総和として定義されます。辺の重みは負になることもあり、そのような辺を取り除くとかえってスコアが増えてしまいます。

ここで求めたいのは、グラフを連結状態に保ったまま不要な辺を削除してスコアを最小化し、「スコアを最大でどれだけ減らせるか」を計算することです。

グラフは配列 edges として与えられ、各要素は {weight, {vertex1, vertex2}}（重みと両端の頂点）という形式で表されます。

入力例と出力

たとえば n = 5、m = 6、edges = {{2, {1, 2}}, {2, {1, 3}}, {1, {2, 3}}, {3, {2, 4}}, {2, {2, 5}}, {1, {3, 5}}} が与えられた場合、出力は 4 となります。

このケースでは、辺 (1, 2) と (2, 5) を取り除くことでスコアが合計 4 減少し、グラフは依然として連結を保っています。

解法のポイント：クラスカル法と Union-Find

この問題は、最小全域木（MST）を構築するクラスカル法と同じ発想で効率よく解けます。鍵となるのは次の観察です。

• 閉路を作る辺は削除できる：両端点がすでに同じ連結成分に属している辺は、取り除いても連結性に影響しません。重みが 0 以上なら削除してスコアを減らせます。
• 全域木が完成した後の正の重みの辺も削除できる：グラフ全体がすでに連結（連結成分数が 1）になっていれば、以降に現れる正の重みの辺はすべて不要です。
• 負の重みの辺は残すのが得：残しておくだけでスコアが下がるため、積極的に保持します。

アルゴリズムの手順

1. 連結成分数 cnum を n で初期化し、各頂点 v に対して make(v)（par[v] = v、dim[v] = 1）を実行します。
2. 辺を重みの昇順にソートします。
3. 各辺 (a, b, weight) について次を判定します。
   • find(a) == find(b)（閉路を形成）なら、weight ≥ 0 であれば res += weight として次の辺へ。
   • cnum == 1（すでにグラフ全体が連結）なら、weight ≥ 0 であれば res += weight。
   • いずれにも該当しなければ unify(a, b) で2つの連結成分を統合します。
4. 最終的な res が「削除によって減らせたスコアの合計」となります。

C++による実装

以下は、経路圧縮とサイズによるマージを行う Union-Find を用いた実装例です。

#include <bits/stdc++.h>
using namespace std;

int cnum = 0;
int par[100];
int dim[100];

void make(int v){
   par[v] = v;
   dim[v] = 1;
}
int find(int v){
   if(par[v] == v)
   return v;
   return par[v] = find(par[v]);
}
void unify(int a, int b){
   a = find(a); b = find(b);
   if(a != b){
      cnum--; if(dim[a] > dim[b]){
         swap(a, b);
      }
      par[a] = b; dim[b] += dim[a];
   }
}
int solve(int n, int m, vector <pair <int, pair<int,int>>> edges){
   cnum = n;
   sort(edges.begin(), edges.end());
   for(int i = 1; i <= n; i++)
      make(i);
   int res = 0;
   for(auto &edge : edges){
      int a = edge.second.first;
      int b = edge.second.second;
      int weight = edge.first;
      if(find(a) == find(b)) {
         if(weight >= 0) 
            res += 1 * weight;
         continue;
      }
      if(cnum == 1){
         if(weight >= 0)
            res += 1 * weight;
      } else{
         unify(a, b);
      }
   }
   return res;
}
int main() {
   int n = 5, m = 6;
   vector <pair<int, pair<int,int>>> edges = {{2, {1, 2}}, {2, {1, 3}}, {1, {2, 3}}, {3, {2, 4}}, {2, {2, 5}}, {1, {3, 5}}};
   cout<< solve(n, m, edges);
   return 0;
}

入力

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

出力

4