计蒜客宝藏 (状压DP)

**链接 : **Here!

**思路 : **

状压DP. 开始想直接爆搜, T掉了, 然后就采用了状压DP的方法来做.
定义$f[S]$为集合$S$的最小代价, $dis[i]$则记录第$i$个点的"深度", 所以说边$E{[i, j]}$ 的工程代价就为$dis[i] * E{[i, j]}$, 因此可以得到状态转移方程 :
- 初始状态(假设以$i$作为起点) :
  - $dis[i] = 1$, $f[1 << (i - 1)] = 0$,
  - $dis[k] = INF (k != i, k = 1, 2, 3 ...)$, $f[k] = INF (k != (1 << (i - 1)), k = 1, 2, ... , (1 << n) - 1)$
- 对于中间状态$j$ :
  - $f[S | 1 << (j - 1)] = min(f[S | 1 << (j - 1)], f[S] + E[i][j] * dis[i])$
  - $dis[j] = dis[i] + 1$
大犇说, 状压为什么快, 是因为在读取数据的时候比普通数组要快... 所以说, 我还是不太理解...为什么快, QAQ, 大犇还说, 世界上总有这么一群人, 你们俩算法复杂度一样, 但他就是比你快几百倍... em....

代码 :

#include <cstdio>
#include <algorithm>
using namespace std;

#define MAX_N 15
const int INF = 0x7FFFFFFF;
int E[MAX_N][MAX_N];
int dis[MAX_N], f[1 << MAX_N];
int n, m;

void init() {
    for (int i = 1 ; i <= n ; ++i) {
        for (int j = 1 ; j <= n ; ++j) {
            E[i][j] = INF;
        }
    }
}
void read() {
    scanf("%d%d", &n, &m);
    init();
    for (int i = 0 ; i < m ; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        E[u][v] = min(E[u][v], w);
        E[v][u] = min(E[v][u], w);
    }
}
void find(int S) {
    for (int i = 1 ; i <= n ; ++i) {
        if (!((1 << (i - 1)) & S)) continue;
        
            for (int j = 1 ; j <= n ; ++j) {
                // if (!((1 << (j - 1) & S) == 0 && E[i][j] != INF)) continue;
                if (!(!(1 << (j - 1) & S) && E[i][j] != INF)) continue;
                if (f[S | (1 << (j - 1))] <= f[S] + dis[i] * E[i][j]) continue;
                f[S | (1 << (j - 1))] = f[S] + dis[i] * E[i][j];
                int t_dis = dis[j];
                dis[j] = dis[i] + 1;
                find(S | (1 << (j - 1)));
                dis[j] = t_dis;
            }
        
    }
}
void solve() {
    int ans = INF;
    for (int i = 1 ; i <= n ; ++i) {
        for (int j = 1 ; j <= n ; ++j) dis[j] = INF;
        for (int j = 1 ; j <= (1 << n) - 1 ; ++j) f[j] = INF;
        dis[i] = 1;
        f[1 << (i - 1)] = 0;
        find(1 << (i - 1));
        ans = min(ans, f[(1 << n) - 1]);
    }
    printf("%d
", ans);
}
int main() {
    read();
    solve();
    return 0;
}

计蒜客 宝藏 (状压DP)

计蒜客宝藏 (状压DP)