抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

ARC078F Mole and Abandoned Mine

This is a picture without description

pufanyi

题解

发布于：Mar 31, 2019

题目链接

给一个 n(n≤15)n(n\le 15) 个点 mm 条边的无向连通图（不存在自环或重边），每条边有一个边权，要求割掉若干条边，使 11 到nn只有 11 条路径（不经过重复点），问割掉的边权和最小是多少。[1]

题解

问题其实就是需要保留的边权和最大。

问题是有关点集 + 路径的，不难想到状态：fi,j​f_{i,j}​表示遍历了集合 i​i​，这条唯一的路径的已经是从1​1​ 到j​j​的答案。

我们考虑选择路径的形状，大概应该应该是这样的：

就是 1∼n1\sim n 的一条，然后中间许多分叉，连向一些连通块，而这些联通块中所有的边都连上。

于是我们考虑转移。

当 j=1j=1 时，fi,j=Eif_{i,j}=E_i，其中 EiE_i 表示 i​i​ 集合中所有边的权值和。

可以连下一个链上的点：fi∖{j},k+dk,j→fi,jf_{i\setminus \{j\},k}+d_{k,j}\to f_{i,j}，就是在 kk 后面新增一个点 jj，当然这个转移的时候dk,jd_{k,j} 应大于00。

还可以从 jj 向一个伸出去一个连通块：fi∖k,j+Ek⋃{j}→fi,jf_{i\setminus k,j}+E_{k\bigcup\{j\}}\to f_{i,j}，当然其中j∉k​j\notin k​。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <bitset>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = 15;
const int inf = 0x3f3f3f3f;

int mmap[maxn][maxn];
LL in[1 << maxn];
LL dp[1 << maxn][maxn];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0, f, t, d; i < m; ++i)
    {
        scanf("%d%d%d", &f, &t, &d);
        mmap[t - 1][f - 1] = mmap[f - 1][t - 1] = d;
    }
    for (int i = 0; i < (1 << n); ++i)
        for (int j = 0; j < n; ++j)
            if (i & (1 << j))
                for (int k = j + 1; k < n; ++k)
                    if (i & (1 << k))
                        in[i] += mmap[j][k];
    for (int i = 0; i < (1 << n); ++i)
        for (int j = 0; j < n; ++j)
            dp[i][j] = -inf;
    for (int i = 0; i < (1 << n); ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (i & (1 << j))
            {
                if (!j)
                    dp[i][j] = in[i];
                else
                {
                    for (int k = 0; k < n; ++k)
                        if (j != k && (i & (1 << k)) && mmap[k][j])
                            dp[i][j] = max(dp[i][j], dp[i ^ (1 << j)][k] + mmap[k][j]);
                    for (int tmp = (i ^ (1 << j)), k = tmp; k; k = (k - 1) & tmp)
                        dp[i][j] = max(dp[i][j], dp[i ^ k][j] + in[k | (1 << j)]);
                }
            }
        }
    }
    printf("%lld\n", in[(1 << n) - 1] - dp[(1 << n) - 1][n - 1]);
    return 0;
}

  1. 翻译来自luogu。 ↩︎

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://pufanyi.github.io/oi-blog/arc078_d/

更新于：Jul 7, 2023

DP

AtCoder

评论