AOJ 2403 The Enemy of My Enemy is My Friend
概要
頂点数の単純無向グラフが与えられる。 また各頂点には値が割り当てられている。 このとき、頂点を含む独立集合のうち値の総和の最大値を求めよ。
制約:
解法
半分全列挙+高速ゼータ変換 (想定解法ではないらしい)。
頂点を半分に分けて、を含む側を、含まない側をとする。 に対して関数をと定めて、 を高速ゼータ変換で求める。
あとは側の独立集合を全列挙しての最大値を返せば良い。 計算量は。
頂点数の単純無向グラフが与えられる。 また各頂点には値が割り当てられている。 このとき、頂点を含む独立集合のうち値の総和の最大値を求めよ。
制約:
半分全列挙+高速ゼータ変換 (想定解法ではないらしい)。
頂点を半分に分けて、を含む側を、含まない側をとする。 に対して関数をと定めて、 を高速ゼータ変換で求める。
あとは側の独立集合を全列挙しての最大値を返せば良い。 計算量は。