AtCoder Regular Contest 078F: Mole and Abandoned Mine

http://arc078.contest.atcoder.jp/tasks/arc078_d

3^Nの形になるdpなんて初めて見た。

まず使う辺に注目して、それらのコストの和を最大化する。
dp[S][v]:=(集合Sの点を使う際で0~v間でpathがただ一つ存在するための最大値)とする。

遷移は二種類ある。
(1)path上の点を追加する。
(2)vにpathが増えないよう点をくっつける。

(1)は問題ないが、(2)は4^Nかかるように見える。
しかし実際は3^Nとなり、適当に定数倍改善すれば十分高速。

なぜ3^Nになるかというと、いま注目すべきものは、
「S⊃T⊃Uとなる(T,U)が何個あるか」という問題と同値である。

各bitについて「Tに選ばれない」「Tにのみ選ばれる」「T,Uともに選ばれる」の三種類があるので、結局(T,U)のペアは3^Nとなる。

int N, M;
int dp[(1 << 16)][16];
int cost[(1 << 16)];
int A[500], B[500], C[500];
int E[50];
int D[50][50];

void solve() {
	cin >> N >> M;
	memset(D, -1, sizeof(D));
	int res = 0;
	rep(i, 0, M) {
		cin >> A[i] >> B[i] >> C[i];
		A[i]--; B[i]--;
		D[A[i]][B[i]] = C[i];
		D[B[i]][A[i]] = C[i];
		res += C[i];
	}
	rep(bit, 0, (1 << N)) {
		rep(j, 0, M) {
			if((bit & (1 << A[j])) && (bit & (1 << B[j]))) {
				cost[bit] += C[j];
			}
		}
	}
	rep(bit, 0, (1 << N)) 
		rep(j, 0, N) dp[bit][j] = -inf;

	dp[1][0] = 0;


	rep(bit, 0, (1 << N)) {
		rep(i, 0, N) {
			if(!(bit & (1 << i)) || dp[bit][i] < 0) continue;
			rep(j, 0, N) {
				if(!(bit & (1 << j)) && D[i][j] != -1) {
					MAX(dp[bit | (1 << j)][j], dp[bit][i] + D[i][j]);
				}
			}
			int n = 0;
			rep(j, 0, N) {
				if(!(bit & (1 << j))) {
					E[n++] = j;
				}
			}
			rep(mask, 0, (1 << n)) {
				int nbit = 0;
				rep(k, 0, n) {
					if(mask & (1 << k)) {
						nbit |= (1 << E[k]);
					}
				}
				MAX(dp[nbit | bit][i], dp[bit][i] + cost[nbit | (1 << i)]);
			}
		}
	}
	int tmp = dp[(1 << N) - 1][N - 1];
	cout << res - tmp << "\n";

}