2288状态压缩dp(tsp问题).cpp

pku 2288 Islands and Bridges 状态压缩DP

#include <iostream>
#define I64 __int64
using namespace std;
//状态为f[i][j][k]，表示经过二进制数i所指的哈密顿路（第bi位为1表示经过该点，为0表示不经过该点），
//倒数第二个点为j，最后一个点为k。.value表示最大权值，.num表示能走出最大权值的路径数。若图中k到p有边，f[i][j][k]则转移到f[i'][k][p]。i' == i | (1 << p)。

struct Node
{
	I64 val, num;
};


int n, m;
I64 c[13];
int g[13][13];
Node f[1<<13][13][13];

void dp(I64 &ans1, I64 &ans2)
{
	if(n == 1){
		ans1 = c[0];
		ans2 = 2;
		return ;
	}
	int i, j, k, p;
	I64 t;
	memset(f, 0, sizeof(f));
	for(i = 0; i < n; i++)			//每两个有边相连的结点
		for(j = 0; j < n; j++) if(g[i][j]){
			f[(1<<i) | (1<<j)][i][j].val = c[i] + c[j] + c[i]*c[j];
			f[(1<<i) | (1<<j)][i][j].num = 1;
		}
	for(i = 0; i < (1<<n); i++){
		for(j = 0; j < n; j++) if((i>>j)&1)	{
			for(k = 0; k < n; k++) if(((i>>k)&1) && f[i][j][k].val != 0){		//j,k结点有边相连
				for(p = 0; p < n; p++) if(((i>>p)&1) == 0 && g[k][p]){			//加入p结点
					t = c[p] + c[p]*c[k];
					if(g[j][p]) t += c[j]*c[k]*c[p];							//如果p,j有边相连
					//更新
					if(f[i][j][k].val + t > f[i|(1<<p)][k][p].val){
						f[i|(1<<p)][k][p].val = f[i][j][k].val + t;
						f[i|(1<<p)][k][p].num = f[i][j][k].num;
					}
					else if(f[i][j][k].val + t == f[i|(1<<p)][k][p].val)		//注意... 相等是方法数增加
						f[i|(1<<p)][k][p].num += f[i][j][k].num;
				}
			}
		}
	}

	ans1 = 0;
	ans2 = 0;
	for(i = 0; i < n; i++){
		for(j = 0; j < n; j++){
			if(f[(1<<n) - 1][i][j].val > ans1){
				ans1 = f[(1<<n) - 1][i][j].val;
				ans2 = f[(1<<n) - 1][i][j].num;
			}
			else if(f[(1<<n) - 1][i][j].val == ans1)
				ans2 += f[(1<<n) - 1][i][j].num;
		}
	}
	return ;
}




int main()
{
	//freopen("data.txt", "r", stdin);
	int ca, i, s, t;
	I64 ans1, ans2;
	scanf("%d", &ca);
	while(ca--){
		scanf("%d%d", &n, &m);
		for(i = 0; i < n; i++)
			scanf("%I64d", &c[i]);
		memset(g, 0, sizeof(g));
		for(i = 0; i < m; i++){
			scanf("%d%d", &s, &t);
			s--;
			t--;
			g[s][t] = g[t][s] = 1;
		}
		dp(ans1, ans2);
		printf("%I64d %I64d\n", ans1, ans2/2);
	}

return 0;
}