题目描述

blablabla

样例

blablabla

算法1

(状压线性dp) $O(2^nn^3)$

$n \leqslant 13$ 诱人得数据量, 直接状压

转移时每次线性向集合添加一个点

而不是向集合中添加一个集合, 区间dp空间不够

然后是要考虑相邻三个点, 故设状态为

f[集合][倒数第二个点][最后一个点]

转移为

f[s][i][j] = max(f[s ^ 1 << k][k][i] + d[i][j] + g[i][][k])

d[i][j] 为预处理的 dis(i, j) 无边为 0

g[i][j][k] 为预处理的三点环权值, 不成环为 0

时间复杂度

参考文献

C++ 代码

ll d[M][M], a[M], g[M][M][M], s;
PLL f[N][M][M];

int main() {
    IOS;
    for (cin >> _; _; --_) {
        cin >> n >> m; s = 0; memset(d, 0, sizeof d); memset(g, 0, sizeof g);
        rep(i, 0, n - 1) cin >> a[i], s += a[i]; memset(f, 0xcf, sizeof f);
        rep(i, 1, m) {
            int u, v; cin >> u >> v; --u, --v;
            if (u ^ v) d[u][v] = d[v][u] = a[u] * a[v],
                f[1 << u ^ 1 << v][u][v] = f[1 << u ^ 1 << v][v][u] = { d[v][u], 1 };
        }
        rep(i, 0, n - 1) rep(j, 0, n - 1) rep(k, 0, n - 1)
            if (d[i][j] && d[j][k] && d[k][i]) g[i][j][k] = a[i] * a[j] * a[k];
        rep(i, 0, (1 << n) - 1) rep(x, 0, n - 1) if (i >> x & 1) rep(y, 0, n - 1)
            if ((y ^ x) && (i >> y & 1) && d[x][y]) rep(k, 0, n - 1)
                if ((y ^ k) && (x ^ k) && (i >> k & 1) && ~f[i ^ 1 << y][k][x].fi)
                    if (umax(f[i][x][y].fi, f[i ^ 1 << y][k][x].fi + d[x][y] + g[k][x][y]))
                        f[i][x][y].se = f[i ^ 1 << y][k][x].se;
                    else if (f[i][x][y].fi == f[i ^ 1 << y][k][x].fi + d[x][y] + g[k][x][y])
                        f[i][x][y].se += f[i ^ 1 << y][k][x].se;
        PII ans = { 0, 0 };
        rep(i, 0, n - 1) rep(j, 0, n - 1) if (i ^ j)
            if (umax(ans.fi, f[(1 << n) - 1][i][j].fi)) ans.se = f[(1 << n) - 1][i][j].se;
            else if (ans.fi == f[(1 << n) - 1][i][j].fi) ans.se += f[(1 << n) - 1][i][j].se;
        cout << ans.fi + (ans.se ? s : 0) << ' ' << ans.se / 2 << '\n';
    }
    return 0;
}