1894.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1894 on 2006-09-04 at 02:48:33 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long int64;
const int N = 13, SN = 1 << N;

int val[SN][N][N], g[N][N], gn[N];
bool cg[N][N];
int64 path[SN][N][N];

int main()
{
	int T, n, m, v[N];

	scanf("%d", &T);
	for(int t = 0; t < T; t++) {
		scanf("%d %d", &n, &m);
		for(int i = 0; i < n; i++) scanf("%d", &v[i]);
		memset(gn, 0, sizeof(gn)); memset(cg, false, sizeof(cg));
		for(int i = 0; i < m; i++) {
			int a, b; scanf("%d %d", &a, &b); a--; b--;
			if(a != b) { g[a][gn[a]++] = b; g[b][gn[b]++] = a; cg[a][b] = cg[b][a] = true; }
		}
		if(n == 1) { printf("%d 1\n", v[0]); continue; }
		int sn = 1 << n;
		memset(val, -1, sizeof(val));
		for(int i = 0; i < n; i++)
			for(int j = 0; j < gn[i]; j++) {
				int k = g[i][j];
				val[(1<<i)|(1<<k)][i][k] = v[i]+v[k]+v[i]*v[k];
				path[(1<<i)|(1<<k)][i][k] = 1;
			}
		for(int i = 0; i < sn; i++) {
			for(int j = 0; j < n; j++) {
				if(!(i&(1<<j)) || i == (1<<j)) continue;
				for(int nk = 0; nk < gn[j]; nk++) {
					int k = g[j][nk];
					if(!(i&(1<<k)) || val[i][j][k] < 0) continue;
					for(int nl = 0; nl < gn[k]; nl++) {
						int l = g[k][nl], st = i|(1<<l);
						if(i&(1<<l)) continue;
						int tmv = val[i][j][k]+v[k]*v[l]+v[l];
						if(cg[j][l]) tmv += v[j]*v[k]*v[l];
						if(tmv > val[st][k][l]) { val[st][k][l] = tmv; path[st][k][l] = path[i][j][k]; }
						else if(tmv == val[st][k][l]) path[st][k][l] += path[i][j][k];
					}
				}
			}
		}
		int64 tv = 0, tp = 0;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				if(tv < val[sn-1][i][j]) { tv = val[sn-1][i][j]; tp = path[sn-1][i][j]; }
				else if(tv == val[sn-1][i][j]) tp += path[sn-1][i][j];
		printf("%lld %lld\n", tv, tp>>1);
	}
	
	return 0;
}