TopCoder SRM 571, Division 1, Level 2 : MagicMolecule

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=11705

概要

頂点に重み付けされた N 頂点からなる無向グラフが与えられる。
このグラフの部分グラフで、頂点数が 以上でクリークとなるものの重みの最大値を求めよ。

解法

N = 50 の場合、求める部分グラフの頂点数は 34 となります。
50 - 34 = 16 なので、問題は「最大 16 個の頂点を取り除く」と言い換えられます。

ある頂点集合 S について、S に含まれる異なる二頂点 u, v 間に辺が無いとき、この二頂点の少なくとも片方は取り除かれる必要があります。
このような頂点 u, v が無いとき、頂点を取り除いても結果は悪くなるだけなので、頂点を取り除く必要はありません。
枝の無い二頂点を見つけたときにだけ、どちらを取り除くかでの分岐が最大 16 回発生します。
すると状態数は となり、探索で解くことができます。

コード

typedef vector<int> VI;
typedef vector<string> VS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) c.begin(), c.end()

class MagicMolecule
{
public:
	VI magicPower;
	VS magicBond;

	int N, minsize;

	int maxMagicPower( vector <int> magicPower, vector <string> magicBond )
	{
		this -> magicPower = magicPower;
		this -> magicBond = magicBond;
		N = magicPower.size();
		minsize = ceil( 2. / 3. * N );
		return dfs( N, vector<bool>( N, false ) );
	}

	int dfs( int rest, vector<bool> vanished )
	{
		if ( rest < minsize )
		{
			return -1;
		}

		REP( i, 0, N )
		{
			REP( j, i + 1, N )
			{
				if ( vanished[i] || vanished[j] || magicBond[i][j] == 'Y' )
				{
					continue;
				}
				int res = -1;
				res = max( res, dfs( rest - 1, setBit( vanished, i ) ) );
				res = max( res, dfs( rest - 1, setBit( vanished, j ) ) );
				return res;
			}
		}

		int res = 0;
		REP( i, 0, N )
		{
			if ( vanished[i] )
			{
				continue;
			}
			res += magicPower[i];
		}
		return res;
	}

	vector<bool> setBit( vector<bool> ary, int pos )
	{
		ary[ pos ] = true;
		return ary;
	}
};