K - ネットワーク敷設 / Network Installation Editorial by admin
gemini-3.5-flash-high概要
\(N\) 頂点 \(M\) 辺の重み付き無向グラフから、ちょうど \(K\) 個の頂点を選択し、それらを連結にするための最小コスト（最小シュタイナー木）を求める問題です。 \(K \leq 5\) という非常に小さい制約を活かし、連結にするための「木の形状（トポロジー）」を分類して全探索することで解くことができます。
考察
最小シュタイナー木と木のトポロジー
選んだ \(K\) 個の頂点を最小コストで連結にするとき、その接続関係は必ず「木」の構造になります。また、選んだ \(K\) 個の頂点は、この木において必ず「葉（次数が1の頂点）」または「途中の頂点」になります。
\(K\) が一般の大きさである場合は「最小シュタイナー木問題」と呼ばれるNP困難な問題になりますが、本問題では \(K \leq 5\) と非常に小さいため、木の形状（トポロジー）をいくつかのパターンに分類し、それぞれの最小コストを全探索で求めることができます。
各 \(K\) における木のトポロジーの分類
\(K\) 個の頂点を葉とする木のトポロジーは、以下のように分類できます。ここで、選ばれる \(K\) 個の頂点を「端点」、それらを繋ぐ分岐点となる頂点を「中心」と呼びます。
\(K = 2\) の場合
- パターン1: 2つの端点 \(u, v\) が直接結ばれる。
- コスト: \(\text{dist}[u][v]\)
- 最小値は、全点対間の最短距離の最小値です。
\(K = 3\) の場合
- パターン1: 1つの中心 \(x\) から3つの端点 \(a, b, c\) が伸びる（スター型）。
- コスト: \(\text{dist}[x][a] + \text{dist}[x][b] + \text{dist}[x][c]\)
- \(x\) を全探索し、各 \(x\) から距離が近い順に3つの頂点を選べば最小になります。
\(K = 4\) の場合
- パターン1: 1つの中心 \(x\) から4つの端点 \(a, b, c, d\) が伸びる。
- 各 \(x\) について、距離が近い順に4つの頂点を選びます。
- パターン2: 2つの中心 \(x, y\) があり、\(x\) から2つの端点 \(a, b\)、\(y\) から2つの端点 \(c, d\) が伸び、さらに \(x\) と \(y\) が結ばれる。
- コスト: \(\text{dist}[x][a] + \text{dist}[x][b] + \text{dist}[x][y] + \text{dist}[y][c] + \text{dist}[y][d]\)
- ただし、\(a, b, c, d\) はすべて異なる頂点である必要があります。
\(K = 5\) の場合
- パターン1: 1つの中心 \(x\) から5つの端点 \(a, b, c, d, e\) が伸びる。
- パターン2: 2つの中心 \(x, y\) があり、\(x\) から3つの端点 \(a, b, c\)、\(y\) から2つの端点 \(d, e\) が伸び、さらに \(x\) と \(y\) が結ばれる。
- コスト: \(\text{dist}[x][a] + \text{dist}[x][b] + \text{dist}[x][c] + \text{dist}[x][y] + \text{dist}[y][d] + \text{dist}[y][e]\)
- パターン3: 3つの中心 \(x, y, z\) があり、パス \(x - y - z\) が形成される。\(x\) から2つの端点 \(a, b\)、\(z\) から2つの端点 \(d, e\) が伸びる（\(y\) は中継点）。
- コスト: \(\text{dist}[x][a] + \text{dist}[x][b] + \text{dist}[x][y] + \text{dist}[y][z] + \text{dist}[z][d] + \text{dist}[z][e]\)
これらすべてのパターンについて最小値を探索し、その中の最小値が答えとなります。
アルゴリズム
1. 全点対間最短経路の計算
まず、任意の2頂点間の最短距離を求める必要があります。制約が \(N \leq 300\)（\(K=5\) のときは \(N \leq 80\)）と小さいため、ワーシャルフロイド法（Warshall-Floyd Algorithm） を用いて \(O(N^3)\) で全点対間最短距離 dist[u][v] を求めます。
2. 近い頂点リストの作成とソート
各頂点 \(u\) について、他のすべての頂点 \(v\) を距離 dist[u][v] の昇順にソートしたリスト L[u] を作成します。
木のトポロジーを探索する際、中心 \(x\) から伸びる端点としては、距離が最も近いものから順に数個だけを候補とすれば十分です（遠い頂点を選ぶとコストが最小にならないため）。具体的には、各リストの先頭から最大で \(K+1\) 個程度（\(K=5\) の場合は最大6個）を考慮すれば、頂点の重複を避けつつ最適な組み合わせを見つけることができます。
3. トポロジーごとの全探索
\(K\) の値に応じて、上記で分類したトポロジーを全探索します。
\(K=4\) のパターン2（2中心）の探索: 2つの中心 \(x, y\) を全探索します。\(x\) から伸びる端点 \(a, b\) を
L[x]の上位5個から選び、\(y\) から伸びる端点 \(c, d\) をL[y]の上位5個から選びます。\(a, b, c, d\) が互いに相異なる場合のみ、コストを計算して最小値を更新します。\(K=5\) のパターン3（3中心）の探索: 3つの中心 \(x, y, z\) を全探索します（\(K=5\) のときは \(N \leq 80\) なので、3重ループ \(O(N^3)\) でも十分に高速です）。\(x\) から端点 \(a, b\) を選び、\(z\) から端点 \(d, e\) を選び、それらが重複しないときにコストを計算します。
計算量
時間計算量
- ワーシャルフロイド法: \(O(N^3)\)
- ソート: 各頂点について \(O(N \log N)\)、全体で \(O(N^2 \log N)\)
- トポロジーの全探索:
- \(K \le 3\): \(O(N)\)
- \(K = 4\):
- パターン1: \(O(N)\)
- パターン2: 2つの中心 \(x, y\) の全探索 \(O(N^2)\)、各ペアに対して定数回（\(5^4\) 回以下）のループ。よって \(O(N^2)\)。
- \(K = 5\)（このとき \(N \leq 80\)）:
- パターン1: \(O(N)\)
- パターン2: 2つの中心 \(x, y\) の探索。定数倍は大きいが \(O(N^2)\)。
- パターン3: 3つの中心 \(x, y, z\) の探索。\(O(N^3)\) 回のループ。各ループ内で定数回の処理。よって \(O(N^3)\)。
全体の最悪時間計算量は \(K=5\) のとき \(O(N^3)\) となり、 \(N \le 80\) の制約下で数ミリ秒で動作します。\(K < 5\) の場合も \(N \le 300\) であり、\(O(N^3)\)（ワーシャルフロイド法がボトルネック）で余裕を持って実行時間制限に間に合います。
空間計算量
- 最短距離を保持するテーブル
distに \(O(N^2)\) - ソートされたリスト
Lに \(O(N^2)\)
全体の空間計算量は \(O(N^2)\) であり、メモリ制限に対しても非常に軽量です。
実装のポイント
頂点の重複防止: 中心から端点を選ぶ際、同じ頂点が異なる端点として選ばれないように、
a == c || a == d || ...のような条件分岐で重複を正しく排除する必要があります。候補数の削減:
L[u]から選ぶ候補の数をmin((int)L[u].size(), 6)のように制限することで、探索する組み合わせの数を大幅に削減し、実行時間を劇的に短縮しています。無限大（INF）の扱い: 到達不可能な経路を誤って足し合わせてオーバーフローしないよう、十分大きな値（
1e16など）をINFとして定義し、加算する前にdist[u][v] == INFのチェックを行っています。ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long INF = 1e16;
int main() {
// Optimize standard I/O operations for competitive programming
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M, K;
if (!(cin >> N >> M >> K)) return 0;
vector<vector<long long>> dist(N + 1, vector<long long>(N + 1, INF));
for (int i = 1; i <= N; ++i) dist[i][i] = 0;
for (int i = 0; i < M; ++i) {
int u, v;
long long w;
cin >> u >> v >> w;
dist[u][v] = min(dist[u][v], w);
dist[v][u] = min(dist[v][u], w);
}
// Warshall-Floyd Algorithm for All-Pairs Shortest Path
for (int k = 1; k <= N; ++k) {
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
// L[u] stores pairs of (distance, vertex_id) sorted by distance from u
vector<vector<pair<long long, int>>> L(N + 1);
for (int u = 1; u <= N; ++u) {
for (int v = 1; v <= N; ++v) {
if (dist[u][v] < INF) {
L[u].push_back({dist[u][v], v});
}
}
sort(L[u].begin(), L[u].end());
}
long long ans = INF;
if (K == 2) {
for (int u = 1; u <= N; ++u) {
for (int v = u + 1; v <= N; ++v) {
ans = min(ans, dist[u][v]);
}
}
} else if (K == 3) {
for (int x = 1; x <= N; ++x) {
if (L[x].size() >= 3) {
ans = min(ans, L[x][0].first + L[x][1].first + L[x][2].first);
}
}
} else if (K == 4) {
// Case 1: 1 center
for (int x = 1; x <= N; ++x) {
if (L[x].size() >= 4) {
ans = min(ans, L[x][0].first + L[x][1].first + L[x][2].first + L[x][3].first);
}
}
// Case 2: 2 centers
for (int x = 1; x <= N; ++x) {
int sz_x = min((int)L[x].size(), 5);
for (int y = 1; y <= N; ++y) {
if (x == y) continue;
long long d_xy = dist[x][y];
if (d_xy == INF) continue;
int sz_y = min((int)L[y].size(), 5);
for (int i = 0; i < sz_x; ++i) {
for (int j = i + 1; j < sz_x; ++j) {
int a = L[x][i].second;
int b = L[x][j].second;
long long cost_x = L[x][i].first + L[x][j].first + d_xy;
for (int k = 0; k < sz_y; ++k) {
for (int l = k + 1; l < sz_y; ++l) {
int c = L[y][k].second;
int d = L[y][l].second;
if (a == c || a == d || b == c || b == d) continue;
ans = min(ans, cost_x + L[y][k].first + L[y][l].first);
}
}
}
}
}
}
} else if (K == 5) {
// Case 1: 1 center
for (int x = 1; x <= N; ++x) {
if (L[x].size() >= 5) {
ans = min(ans, L[x][0].first + L[x][1].first + L[x][2].first + L[x][3].first + L[x][4].first);
}
}
// Case 2: 2 centers
for (int x = 1; x <= N; ++x) {
int sz_x = min((int)L[x].size(), 6);
for (int y = 1; y <= N; ++y) {
if (x == y) continue;
long long d_xy = dist[x][y];
if (d_xy == INF) continue;
int sz_y = min((int)L[y].size(), 6);
for (int i = 0; i < sz_x; ++i) {
for (int j = i + 1; j < sz_x; ++j) {
for (int k = j + 1; k < sz_x; ++k) {
int a = L[x][i].second;
int b = L[x][j].second;
int c = L[x][k].second;
long long cost_x = L[x][i].first + L[x][j].first + L[x][k].first + d_xy;
for (int l = 0; l < sz_y; ++l) {
for (int m = l + 1; m < sz_y; ++m) {
int d = L[y][l].second;
int e = L[y][m].second;
if (a == d || a == e || b == d || b == e || c == d || c == e) continue;
ans = min(ans, cost_x + L[y][l].first + L[y][m].first);
}
}
}
}
}
}
}
// Case 3: 3 centers
for (int x = 1; x <= N; ++x) {
int sz_x = min((int)L[x].size(), 5);
for (int z = 1; z <= N; ++z) {
if (x == z) continue;
if (dist[x][z] == INF) continue;
int sz_z = min((int)L[z].size(), 5);
for (int i = 0; i < sz_x; ++i) {
for (int j = i + 1; j < sz_x; ++j) {
int a = L[x][i].second;
int b = L[x][j].second;
long long cost_xz = L[x][i].first + L[x][j].first;
for (int k = 0; k < sz_z; ++k) {
for (int l = k + 1; l < sz_z; ++l) {
int d = L[z][k].second;
int e = L[z][l].second;
if (a == d || a == e || b == d || b == e) continue;
long long cost_all = cost_xz + L[z][k].first + L[z][l].first;
for (int y = 1; y <= N; ++y) {
if (y == x || y == z) continue;
if (a == y || b == y || d == y || e == y) continue;
long long d_xy = dist[x][y];
long long d_yz = dist[y][z];
if (d_xy == INF || d_yz == INF) continue;
ans = min(ans, cost_all + d_xy + d_yz);
}
}
}
}
}
}
}
}
cout << ans << "\n";
return 0;
}
この解説は gemini-3.5-flash-high によって生成されました。
posted:
last update: