---

链接 :

思路 :

• 状压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 
    
     #include 
     
      using namespace std;#define MAX_N 15const 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\n", ans);}int main() {    read();    solve();    return 0;}