Description

题目链接

题目大意:求给定图的最小生成树,其中每条边的代价为该边的长度和起点到这条边起点的点的个数的乘积。$1 \le n \le 12$。

Solution

最小生成树且每次加一个点,不难想到 Prim。

然而由于每条边的代价的不确定的,因此正确性不能保证。

对于 $70 \%$ 的数据,枚举全排列然后爆搜即可。

对于 $100 \%$ 的数据,看到这么小的数据范围,很容易让人有状压的直觉。

设 $f(S)$ 表示已经包含了 $S$ 的最小代价,转移也是十分显然的,枚举 $i \in S, j \not \in S$,然后更新 $f(S \cup \{j\})$ 即可。

由于不知道起点,需要枚举起点后再 dfs。

时间复杂度估摸着是个 $O(n3^n)$ 的样子,由于 $n \le 12$,随便过了。

好像可以用模拟退火或者神奇的剪枝跑的飞快。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <set>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef long long LL;
typedef unsigned long long uLL;

int g[20][20];
int f[(1 << 12) + 10], dis[20];
int n, m, ans = 2e9;

void dfs(int s) {
    for (int i = 1; i <= n; ++i) {
        if (s & (1 << (i - 1))) {
            for (int j = 1; j <= n; ++j) {
                if ((!(s & (1 << (j - 1)))) && g[i][j] != 2e9 && f[s | (1 << (j - 1))] > f[s] + g[i][j] * dis[i]) {
                    f[s | (1 << (j - 1))] = f[s] + g[i][j] * dis[i];
                    int w = dis[j];
                    dis[j] = dis[i] + 1;
                    dfs(s | (1 << (j - 1)));
                    dis[j] = w;
                }
            }
        }
    }
}

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            g[i][j] = 2e9;
        }
    }
    for (int i = 1, u, v, w; i <= m; ++i) {
        read(u), read(v), read(w);
        g[u][v] = g[v][u] = std::min(g[u][v], w);
    }
    for (int i = 1; i <= n; ++i) {
        memset(dis, 0x3f3f3f3f, sizeof(dis));
        memset(f, 0x3f3f3f3f, sizeof(f));
        f[1 << (i - 1)] = 0;
        dis[i] = 1;
        dfs(1 << (i - 1));
        ans = std::min(ans, f[(1 << n) - 1]);
    }
    printf("%d\n", ans);
    return 0;
}
Last modification:November 16th, 2021 at 08:16 pm