SRM622D1Med EtherNet
これが450ptじゃないの不思議
問題概要(原文)
$N$ 頂点のツリーグラフが与えられる．辺は長さを持つ． 辺を爆破して，どの点どうしの最短距離も $d$ 以下であるようにしたい．何本爆破する必要があるか？
考察
$u$ を根とする部分木に関するグラフを考える．親から最も遠い頂点への距離 $x$ とする．
$u$ の子 $v$ を根とする部分木とのマージを考える．このとき， 親から最も遠い頂点への距離を $y$ とし， $u,v$ をつなぐ辺の長さを $z$ とする．
$x+y+z \leq d$ ならば直径は $d$ 以下なので切らなくてもよい(切ってもよい)．そうでないならば必ずこの辺は切らないといけない．
これを全ての頂点を根として試してやる．計算量は $O(N^{2} d^{2} )$ だが，若干の枝刈りでかなりの高速化ができる．
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class Ethernet
{
public int connect(int[] parent, int[] dist, int d)
{
var n = parent.Length + 1;
var G = Enumerate(n, x => new List<KeyValuePair<int, int>>());
for (int i = 0; i < n - 1; i++)
{
G[parent[i]].Add(new KeyValuePair<int, int>(i + 1, dist[i]));
G[i + 1].Add(new KeyValuePair<int, int>(parent[i], dist[i]));
}
Func<int, int, int[]> dfs = null;
dfs = (prev, cur) =>
{
var ret = new int[d + 1];
for (int i = 1; i <= d; i++)
ret[i] = 100000;
foreach (var e in G[cur])
{
if (e.Key == prev) continue;
var res = dfs(cur, e.Key);
var next = new int[d + 1];
for (int i = 0; i <= d; i++)
next[i] = 100000;
for (int i = 0; i <= d; i++)
{
if (ret[i] >= 100) continue;
for (int j = 0; j <= d; j++)
{
if (res[j] >= 100) continue;
if (i + j + e.Value > d)
next[i] = Math.Min(next[i], ret[i] + res[j] + 1);
else
{
next[Math.Max(i, j + e.Value)] = Math.Min(next[Math.Max(i, j + e.Value)], ret[i] + res[j]);
next[i] = Math.Min(next[i], ret[i] + res[j] + 1);
}
}
}
ret = next;
}
return ret;
};
var min = 100000;
for (int i = 0; i < n; i++)
min = Math.Min(min, dfs(-1, i).Min());
return min + 1;
}
}
コメント
- これは本当に典型だと思う
