【第11题】题解及代码分享：状压DP，嗅大了，[ABC318D] General Weighted Max Matching

2023-11-22 14:59:40 浏览数 (2)

大家好，我是小码匠，今天分享的是一道状压DP的题目。

小插曲

老码农让我先用DFS实现，之后在用状压DP。

我麻溜的写完DFS顺利的AC掉，之后开始写状压DFS版代码，然后测了几组数据就直接提交了。

直接告诉老码农AC掉了。

后来老码农在给我整理代码时，发现还是调用的: best_coder方法，真是糗大了，结果一放开：happy_coder就挂掉了。

后来又调试了一会才AC掉。

代码语言：javascript复制
int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}

前置知识

  • 状压DP

路漫漫其修远兮，吾将上下而求索

离自己的既定目标：

  • 目标：300道
  • 已完成：11道
  • 待完成：289道

题目描述

官方原题：

  • https://atcoder.jp/contests/abc318/tasks/abc318_d
  • 洛谷：https://www.luogu.com.cn/problem/AT_abc318_d

题意简述

有一个无向图，i 到 j 的距离为

D_{i,j}

。你可以选择一些边，使得这些边连接的所有顶点互不相同。求这些边总长度的最大值。

输入格式

以以下格式输入：

  • N
D_{1,2},D_{1,3},…,D_{1,N}
D_{2,3,}…,D_{2,N}
  • ⋮
D_{N−1,N}

输出格式

1 个整数。如题意。

提示

  • 2≤N≤16
  • 1≤
D_i,j

≤

10^9

样例一解释

选择

D_{1,3},D_{2,4}

，总和为5 8=13。

输入输出样例

输入 #1复制

代码语言：javascript复制
4
1 5 4
7 8
6

输出 #1

代码语言：javascript复制
13

输入 #2

代码语言：javascript复制
3
1 2
3

输出 #2

代码语言：javascript复制
3

输入 #3

代码语言：javascript复制
16
5 6 5 2 1 7 9 7 2 5 5 2 4 7 6
8 7 7 9 8 1 9 6 10 8 8 6 10 3
10 5 8 1 10 7 8 4 8 6 5 1 10
7 4 1 4 5 4 5 10 1 5 1 2
2 9 9 7 6 2 2 8 3 5 2
9 10 3 1 1 2 10 7 7 5
10 6 1 8 9 3 2 4 2
10 10 8 9 2 10 7 9
5 8 8 7 5 8 2
4 2 2 6 8 3
2 7 3 10 3
5 7 10 3
8 5 7
9 1
4

输出 #3

代码语言：javascript复制
75
输入数据1
代码语言：javascript复制
6 5
1 1 1 2 2 3
1 2
6 4
5 1
3 6
4 6

题解

  • https://www.luogu.com.cn/problem/solution/AT_abc318_d
赛场代码
AC代码：DFS
代码语言：javascript复制
#include <bits/stdc  .h>

using namespace std;


const int maxn = 20;
int n, g[maxn][maxn];
long long ans = 0;
bool vis[maxn];

void dfs(int u, long long sum) {
    if (u > n) {
        ans = max(ans, sum);
        return;
    }
    if (!vis[u]) {
        vis[u] = true;
        for (int i = u   1; i <= n;   i) {
            if (!vis[i]) {
                vis[i] = true;
                dfs(u   1, sum   g[u][i]);
                vis[i] = false;
            }
        }
        vis[u] = false;
    }
    dfs(u   1, sum);
}

void best_coder() {
    cin >> n;
    for (int i = 1; i < n;   i) {
        for (int j = i   1; j <= n;   j) {
            int d;
            cin >> d;
            g[i][j] = g[j][i] = d;
        }
    }
    dfs(1, 0);
    cout << ans;
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}
AC代码：状压DP
代码语言：javascript复制
#include <bits/stdc  .h>

using namespace std;

const int maxn = 20;
int n, g[maxn][maxn];
long long ans = 0;
bool vis[maxn];

long long dp[1 << 17];

void happy_coder() {
    cin >> n;
    for (int i = 0; i < n - 1;   i) {
        for (int j = i   1; j < n;   j) {
            cin >> g[i][j];
        }
    }
    for (int i = 0; i < (1 << n);   i) {
        for (int j = 0; j < n;   j) {
            if (i & (1 << j)) {
                for (int s = j   1; s < n;   s) {
                    if (i & (1 << s)) {
                        dp[i] = max(dp[i ^ (1 << j) ^ (1 << s)]   g[j][s], dp[i]);
                    }
                }
            }
        }
    }
    for (int i = 0; i < (1 << n);   i) {
        ans = max(ans, dp[i]);
    }
    cout << ans;
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    //best_coder();

    // 最优解
    happy_coder();

    return 0;
}

END

dp int matching max 效率

0 人点赞