SRM695D1Med BearKRoads
errichtoセットだった．
問題概要(原文)
$N(1 \leq N \leq 1000)$ 頂点， $M(1 \leq M \leq 1000)$ 本の辺からなる単純無向グラフがある．頂点 $i$ は自然数 $a_i(1 \leq a_i \leq 999)$ を持つ． グラフの次数の最大値は $3$ である．
$K(1 \leq K \leq 7)$ 本の辺を選ぶ．選んだ辺に含まれる頂点たちが持つ自然数の総和が得点となる．
得点の最大値を求めよ．
考察
greedyに得点が大きい辺 $u-v$ を選ぶことを考える．これは明らかにダメ．
しかし，そのような場合， $x-u,v-y$ となるように選ぶのが最適である． このような選び方は何通りあるかというと， $5$ 通りしかない(次数の最大値がたかだか $3$ なので) ${u-v },{ a-u,v-x }, { b-u,v-x },{a-u,v-y }, {b-u,v-y }$．
$50$ 本程度の辺について使うかどうかを全探索するだけでも十分に間に合う．
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class BearKRoads
{
public int maxHappy(int[] p, int[] a, int[] b, int K)
{
var n = p.Length;
var m = a.Length;
var G = Enumerate(n, x => new List<int>());
for (int i = 0; i < a.Length; i++)
{
G[a[i]].Add(b[i]);
G[b[i]].Add(a[i]);
}
var id = Enumerate(m, x => x);
Array.Sort(id, (l, r) =>
{
var u = p[a[l]] + p[b[l]];
var v = p[a[r]] + p[b[r]];
return v.CompareTo(u);
});
var max = 0;
Func<int, int[], int, int, int> dfs = null;
dfs = (ptr, used, cnt, sum) =>
{
if (ptr == m || ptr == 48 || cnt == K)
{
max = Math.Max(max, sum);
return 0;
}
dfs(ptr + 1, used, cnt, sum);
var u = a[id[ptr]];
var v = b[id[ptr]];
var nsum = sum;
if (used[u] == 0) nsum += p[u];
if (used[v] == 0) nsum += p[v];
used[u]++; used[v]++;
dfs(ptr + 1, used, cnt + 1, nsum);
used[u]--;used[v]--;
return 0;
};
dfs(0, new int[n], 0, 0);
return max;
}
static public T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
}
コメント
- Errichto問題を解きまくっていたからか，そこまで手こずらなかった
- こういうad-hocな探索が時間内にきっちり解けるのは成長を感じる
