PKU 2288 Islands and Bridges

問題

n頂点からなる無向グラフが与えられる。
頂点にはそれぞれ値x[i]がついている。

このグラフのハミルトンパス（全ての頂点を1度ずつ通るパス）のうち、
次のスコアを最大にするパスのスコアおよび、総数を出力せよ。
ハミルトンパスが存在しないときは0 0を出力せよ。

スコア：
ハミルトンパスをc1,c2,c3...,cnとする。
頂点ciの値をv[i]とするとき、スコアは次の式で与えられる。
Σv[i] + Σv[i] * v[i - 1] + Σ[ciとci-2の間に辺があるi]v[i] * v[i - 1] * v[i - 2]

制約条件

n≦13
v[i]≦100
逆順にして重なるパスは同一とみなす。

方針

dp[mask][i][j]を、今までにmaskの都市を訪問して、現在iにいて、直前にjにいたときの
今までのスコアの最大値とするようなビットDPをすればよい。
同時にway[mask][i][j]も使って場合の数も求めてやる。

逆順のパスも数えてしまっているので、全体を2で割る。
ただしn = 1のときはコーナーケースで、このときは2で割らない。

ソースコード

int n, m, v[20];
bool e[20][20];
int dp[1 << 13][13][13];
ll way[1 << 13][13][13];

int main(){
	int cs;
	cin >> cs;
	while(cs--){
		cin >> n >> m;
		rep(i, n) rep(j, n) e[i][j] = 0;
		rep(i, n) cin >> v[i];
		rep(i, m){
			int x, y;
			cin >> x >> y;
			e[--x][--y] = 1;
			e[y][x] = 1;
		}
		rep(i, 1 << n) rep(j, n) rep(k, n) dp[i][j][k] = -1e9, way[i][j][k] = 0;
		rep(i, n) dp[1 << i][i][i] = 0, way[1 << i][i][i] = 1;
		
		rep(i, 1 << n) rep(j, n) rep(k, n) if(way[i][j][k]) rep(l, n){
			if((i & 1 << l) || !e[j][l]) continue;
			int ni = i | 1 << l, nc = dp[i][j][k] + v[j] * v[l];
			
			if(j != k && e[k][l]) nc += v[j] * v[k] * v[l];
			if(dp[ni][l][j] < nc) dp[ni][l][j] = nc, way[ni][l][j] = 0;
			if(dp[ni][l][j] == nc) way[ni][l][j] += way[i][j][k];
		}
		
		int ans = 0; ll cnt = 0;
		rep(i, n) rep(j, n){
			if(ans < dp[(1 << n) - 1][i][j]) ans = dp[(1 << n) - 1][i][j], cnt = 0;
			if(ans == dp[(1 << n) - 1][i][j]) cnt += way[(1 << n) - 1][i][j];
		}
		if(cnt) rep(i, n) ans += v[i];
		if(n == 1) cnt = 2;
		cout << ans << " " << cnt / 2 << endl;
	}
	return 0;
}