[NOIP 2017] 宝藏

[题目链接]

           http://uoj.ac/problem/333

[算法]

        状压DP

        f[i][j][S]表示j的深度为i，要从第j个宝藏屋开始挖，挖出集合S的最小代价

        有状态转移方程 ：

        f[i][j][S] = min{ (i + 1) * dist(j,k) + f[i + 1][k][S2 - {k}] + f[i][j][S - S2] } （ 其中，S2为S的子集）

        具体实现时需要枚举子集

[代码]

        

#include<bits/stdc++.h>
using namespace std;
#define MAXN 12

const int MAXS = 1 << 12;
const int INF = 1e9;

int i,j,k,mask,cost,u,v,w,t1,t2,ans,n,m,S,S2;
int dist[MAXN][MAXN];
int f[MAXN][MAXN][MAXS];
int bit[MAXN],size[MAXS];

int main()
{
        
        scanf("%d%d",&n,&m);
        for (i = 0; i < n; i++)
        {
                for (j = 0; j < n; j++)
                {
                        dist[i][j] = INF;
                }
        }
        for (i = 1; i <= m; i++)
        {
                scanf("%d%d%d",&u,&v,&w);
                u--; v--;
                dist[u][v] = dist[v][u] = min(dist[u][v],w);
        }
        mask = (1 << n) - 1;
        for (i = 0; i < n; i++)
        {
                for (j = 0; j < n; j++)
                {
                        for (k = 0; k <= mask; k++)
                        {
                                f[i][j][k] = INF;
                        }
                }
        }
        bit[0] = 1;
        for (i = 1; i < n; i++) bit[i] = bit[i - 1] << 1;
        for (i = 1; i < n; i++) size[i] = size[(i - 1) & i] + 1;
        for (i = 0; i < n; i++) f[n - 1][i][0] = 0;
        for (i = 0; i <= n - 2; i++)
        {
                for (j = 0; j < n; j++)
                {
                        f[i][j][0] = 0;
                }
        }
        for (i = n - 2; i >= 0; i--)
        {
                for (j = 0; j < n; j++)
                {
                        for (S = 1; S <= mask; S++)
                        {
                                if (size[S] > n - i - 1) continue;
                                for (k = 0; k < n; k++)
                                {
                                        if (dist[j][k] == INF) continue;
                                        cost = dist[j][k] * (i + 1);
                                        v = INF;
                                        if (!(S & bit[k])) continue;
                                        for (S2 = S; S2; S2 = (S2 - 1) & S)
                                        {
                                                if (!(S2 & (1 << k))) continue;
                                                t1 = f[i + 1][k][S2 ^ bit[k]];
                                                t2 = f[i][j][S ^ S2];
                                                if (t1 + t2 < v) v = t1 + t2;
                                        }
                                        if (cost + v < f[i][j][S]) f[i][j][S] = cost + v;
                                }
                        }
                }
        }
        ans = INF;
        for (i = 0; i < n; i++) ans = min(ans,f[0][i][mask ^ bit[i]]);
        printf("%d
",ans);
        
        return 0;
}