AT2657 [ARC078D] Mole and Abandoned Mine

简要题解如下：

记 \(1\) 到 \(n\) 的路径为关键路径。

注意到关键路径只有一条是解题的关键，可以思考这张图长什么样子。
不难发现关键路径上所有边均为桥，因此大致上是关键路径上每个点下面挂了很多个连通块。
基于这张图的形态涉及一个 \(dp\)，令 \(f_{i, S}\) 表示当前只考虑 \(S\) 这个集合，当前在关键路径上走到的点为 \(i\) 留下的最大边权。
转移有两种，一种是直接考虑在关键路径上往后扩展一个点 \(j\)，令一种方式是考虑在 \(i\) 下面挂上一个连通块 \(T\) 此处可以枚举子集。通过预处理等技巧可以做到 \(\mathcal{O(n ^ 2 2 ^ n + n 3 ^ n)}\)

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for (int i = l; i <= r; ++i)

const int N = 20;

const int M = (1 << 15) + 5;

int n, m, u, v, c, L, all, g[M], w[N][N], f[N][M], dp[N][M];

int main () {

    cin >> n >> m, L = (1 << n) - 1;

    memset(w, 128, sizeof(w)), memset(dp, 128, sizeof(dp));

    rep(i, 1, m) cin >> u >> v >> c, w[u][v] = w[v][u] = c, all += c;

    rep(S, 0, L) rep(i, 1, n) rep(j, 1, n) if((1 << (j - 1)) & S) f[i][S] += max(0, w[i][j]);

    rep(S, 0, L) {

        rep(i, 1, n) rep(j, 1, n) if(((1 << (i - 1)) & S) && ((1 << (j - 1)) & S)) g[S] += max(0, w[i][j]);

        g[S] /= 2;

    }

    dp[1][1] = 0;

    rep(S, 0, L) rep(i, 1, n) if(dp[i][S] >= 0) {

        rep(j, 1, n)

            if(!((1 << (j - 1)) & S) && w[i][j] > 0)

                dp[j][S | (1 << (j - 1))] = max(dp[j][S | (1 << (j - 1))], dp[i][S] + w[i][j]);

        for (int T = (L ^ S); T; T = ((T - 1) & (L ^ S)))

            dp[i][S | T] = max(dp[i][S | T], dp[i][S] + f[i][T] + g[T]);

    }

    printf("%d", all - dp[n][L]);

    return 0;

}

一定要将思路理清，考虑最终状态的时候一定要完全准确，否则可能会出现某些性质没有发现的情况。

巴特西

AT2657 [ARC078D] Mole and Abandoned Mine

最新文章

热门文章