题意：n个点，m有向边，w[i]表示i的价值，求价值最大的哈密顿图（只经过所有点一次）。价值为：所有点的w之和，加上，每条边的价值 = w[i] * w[j]，加上，如果连续的三个点相互连接的价值 = w[i] * w[j] * w[k]。不存在输出0 0。n <= 13。
思路：dp[state][i][j]表示state状态下，最后两个为i，j。
代码：
#include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned long long ull; const double eps = 1e-8; const int maxn = 15 + 10; const int M = maxn * 30; const ull seed = 131; const int INF = 0x3f3f3f3f; const int MOD = 1e4 + 7; int w[maxn]; int n, m; int g[maxn][maxn]; int dp[(1 << 13) + 10][maxn][maxn]; ll way[(1 << 13) + 10][maxn][maxn]; void solve(){ memset(dp, -1, sizeof(dp)); memset(way, 0, sizeof(way)); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(i == j) continue; if(g[i][j] == INF) continue; dp[(1 << i) | (1 << j)][i][j] = w[i] + w[j] + g[i][j]; way[(1 << i) | (1 << j)][i][j]++; } } for(int t = 0; t < (1 << n) - 1; t++){ for(int i = 0; i < n; i++){ if(!((1 << i) & t)) continue; for(int j = 0; j < n; j++){ if(!((1 << j) & t)) continue; if(g[i][j] == INF) continue; if(dp[t][i][j] == -1) continue; for(int k = 0; k < n; k++){ if((1 << k) & t) continue; if(g[j][k] == INF) continue; ll ret = dp[t][i][j] + w[k] + g[j][k]; if(g[i][k] != INF) ret += w[i] * w[j] * w[k]; if(dp[(1 << k) | t][j][k] < ret){ dp[(1 << k) | t][j][k] = ret; way[(1 << k) | t][j][k] = way[t][i][j]; } else if(dp[(1 << k) | t][j][k] == ret){ way[(1 << k) | t][j][k] += way[t][i][j]; } } } } } } int main(){ int T; scanf("%d", &T); while(T--){ scanf("%d%d", &n, &m); for(int i = 0; i < n; i++) scanf("%d", &w[i]); memset(g, INF, sizeof(g)); for(int i = 0; i < m; i++){ int u, v; scanf("%d%d", &u, &v); u--, v--; g[u][v] = g[v][u] = w[u] * w[v]; } if(n == 1){ printf("%d 1\n", w[0]); continue; } solve(); ll ans = 0, num = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(i == j) continue; if(g[i][j] == INF) continue; if(dp[(1 << n) - 1][i][j] > ans){ ans = dp[(1 << n) - 1][i][j]; num = way[(1 << n) - 1][i][j]; } else if(dp[(1 << n) - 1][i][j] == ans){ num += way[(1 << n) - 1][i][j]; } } } printf("%lld %lld\n", ans, num / 2); } return 0; } /* 3 3 1 2 2 2 1 2 */
手机扫一扫
移动阅读更方便
你可能感兴趣的文章
4
5
6
7
8
9
10
