题解：P12593 沉石鱼惊旋

做题需要先看数据范围。发现

n\leq 8

，显然我们可以枚举全排列枚举删除顺序。使用打删除标记遍历每一条边来模拟题意。

枚举全排列可以使用 next_permutation 或 DFS 搜索（如 std）。

m

是

n^2

级别的，故复杂度

\mathcal O(n! n^2)

。

当然本题也可以通过状态压缩 DP 做到

\mathcal O(2^n n^2)

的复杂度。

开

n=8

是因为放在这个位置被钦定使用枚举全排列通过，作者写了一份 Python 代码发现

n=9

就跑的很慢了。

另外 C++ 注意要开 long long，其他语言同理。

第一档部分分每次选度数最小的出来做。第二档其实也是，但是因为树的特殊性质边权之和就是答案。

刻意卡了一下每次选度数最小或者是代价最小的拉出来跑贪心或者凭这个性质做搜索的剪枝。分别被卡到了

70

分和

60

分。

关于题目名称，和本场比赛彩蛋有关。

这是我写的 std。

CPP

// std
#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chkmn(T &x, T y) { x = min(x, y); }
typedef long long ll;
int n, m;
vector<array<int, 2>> a[30];
bool vis[30];
bool del[30];
int v[30];
ll ans = 1e18;
void dfs(int dep)
{
    if (dep == n + 1)
    {
        memset(del, 0, sizeof(del));
        ll tmp = 0;
        for (int i = 1; i <= n; i++)
        {
            int u = v[i];
            int tot = 0;
            ll sum = 0;
            for (auto [v, w] : a[u])
            {
                if (del[v])
                    continue;
                tot++;
                sum += w;
            }
            del[u] = 1;
            tmp += sum * tot;
        }
        chkmn(ans, tmp);
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (vis[i])
            continue;
        v[dep] = i;
        vis[i] = 1;
        dfs(dep + 1);
        vis[i] = 0;
        v[dep] = 0;
    }
}
int main()
{
    cin >> n >> m;
    while (m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        a[u].push_back({v, w});
        a[v].push_back({u, w});
    }
    dfs(1);
    cout << ans << '\n';
    return 0;
}

用 GPT 4o 写了个代码结果常数太大过不去，比我写的这份慢了十倍。

PYTHON

# Python std
n, m = map(int, input().split())
e = [[]]
for i in range(n + 1):
    t = []
    for j in range(n + 1):
        t.append(-1)
    e.append(t)
for i in range(m):
    u, v, w = map(int, input().split())
    e[u][v] = e[v][u] = w
vis = [0] * (n + 1)
vv = [-1] * (n + 1)

ans = 10**18


def dfs(dep):
    global ans
    if dep == n + 1:
        dele = [0] * (n + 1)
        tmp = 0
        for i in range(1, n + 1):
            u = vv[i]
            tot = 0
            sum = 0
            for v in range(1, n + 1):
                if e[u][v] == -1:
                    continue
                if dele[v]:
                    continue
                tot += 1
                sum += e[u][v]
            dele[u] = 1
            tmp += sum * tot
        ans = min(ans, tmp)
        return
    for u in range(1, n + 1):
        if vis[u]:
            continue
        vis[u] = 1
        vv[dep] = u
        dfs(dep + 1)
        vis[u] = 0
        vv[dep] = -1


dfs(1)
print(ans)

这份是 GPT 4o 写的 Java 代码。

JAVA

// GPT 4o Java

import java.util.*;

public class Main {
    static int n, m;
    static List<int[]>[] graph;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; ++i) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; ++i) {
            int u = sc.nextInt(), v = sc.nextInt(), w = sc.nextInt();
            graph[u].add(new int[]{v, w});
            graph[v].add(new int[]{u, w});
        }

        int[] order = new int[n];
        for (int i = 0; i < n; ++i) order[i] = i + 1;

        long ans = Long.MAX_VALUE;

        do {
            // 深复制图结构
            List<int[]>[] g = new ArrayList[n + 1];
            for (int i = 1; i <= n; ++i) {
                g[i] = new ArrayList<>();
                for (int[] edge : graph[i]) {
                    g[i].add(new int[]{edge[0], edge[1]});
                }
            }

            boolean[] deleted = new boolean[n + 1];
            long cost = 0;

            for (int idx = 0; idx < n; ++idx) {
                int u = order[idx];
                int deg = 0;
                long sum = 0;

                for (int[] edge : g[u]) {
                    int v = edge[0], w = edge[1];
                    if (!deleted[v]) {
                        deg++;
                        sum += w;
                    }
                }

                cost += (long) deg * sum;
                deleted[u] = true;

                for (int[] edge : g[u]) {
                    int v = edge[0];
                    g[v].removeIf(e -> e[0] == u);
                }

                g[u].clear();
            }

            ans = Math.min(ans, cost);

        } while (nextPermutation(order));

        System.out.println(ans);
    }

    // Java 没有内建的 next_permutation，需要手写
    static boolean nextPermutation(int[] arr) {
        int i = arr.length - 2;
        while (i >= 0 && arr[i] >= arr[i + 1]) i--;
        if (i < 0) return false;

        int j = arr.length - 1;
        while (arr[j] <= arr[i]) j--;
        swap(arr, i, j);
        reverse(arr, i + 1, arr.length - 1);
        return true;
    }

    static void swap(int[] arr, int i, int j) {
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }

    static void reverse(int[] arr, int l, int r) {
        while (l < r) swap(arr, l++, r--);
    }
}

题解：P12593 沉石鱼惊旋

文章操作

相关推荐

评论

题解：P12593 沉石鱼惊旋