[NOIP2017]宝藏子集DP

题面：[NOIP2017]宝藏

题面：

　　首先我们观察到，如果直接DP，因为每次转移的代价受上一个状态到底选了哪些边的影响，因此无法直接转移。

　　所以我们考虑分层DP，即每次强制现在加入的点的距离为k（可能实际上小于k），这样就可以忽略掉上个状态选了哪些边的影响了。

　　所以这样为什么是正确的呢？

　　设f[i][j]表示DP到第i层，状态为j的最小代价。（即每层离起点最远的点的距离为i - 1，所以下次转移的点距离为i）

　　那么如果一个点被错误的计算了代价，当且仅当这个点离起点的距离小于i，但我们依然按照i的距离来计算了代价。

　　那么可以证明，这个点一定会在正确的层数被计算一次（i之前的某一层），那么由于当前层数导致代价被多算，因此肯定没那么优，所以不会对答案造成影响。

　　因此我们直接DP即可。

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define AC 15

 #define ac 12000

 #define inf 2139062143

 #define LL long long

 int n, m, maxn, ans = inf;

 int f[AC][ac], in[AC], g[AC][AC], dis[ac][AC];

 inline int read()

 {

     int x = ;char c = getchar();

     while(c > '' || c < '') c = getchar();

     while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

     return x;

 }

 inline void upmin(int &a, int b){

     if(b < a) a = b;

 }

 void pre()

 {

     n = read(), m = read(), maxn = ( << n) - ;

     memset(g, , sizeof(g));

     for(R i = ; i <= m; i ++)

     {

         int a = read(), b = read(), c = read();

         upmin(g[a][b], c), upmin(g[b][a], c);

     }

     int tmp = ;

     for(R i = ; i <= n; i ++)

         in[i] = tmp, tmp <<= , g[i][i] = ;

 }

 void get()//获取所有联通块到各个点的距离，预处理可以降低复杂度

 {

     memset(dis, , sizeof(dis));

     for(R k = ; k <= maxn; k ++)

     {

         for(R i = ; i <= n; i ++)//枚举集合内的一点

         {

             if(!(k & in[i])) continue;

             for(R j = ; j <= n; j ++)

             {

                 if(k & in[j]) dis[k][j] = ;

                 else upmin(dis[k][j], g[i][j]);

             }

         }

     }

 }    

 void work()

 {

     memset(f, , sizeof(f));

     for(R k = ; k <= n + ; k ++)//枚举当前层(走下一步的最远距离)

     {

         for(R i = ; i <= n; i ++) f[k][in[i]] = ;

         upmin(ans, f[k][maxn]);

         for(R i = ; i <= maxn; i ++)//枚举状态

         {

             if(f[k][i] == inf) continue;//不判断这个可能会爆int

             int s = i ^ maxn;//获取补集

             for(R j = s; j; j = (j - ) & s)//枚举补集的子集

             {

                 int tmp = ;bool flag = true;

                 for(R l = ; l <= n; l ++)

                 {

                     if(!(j & in[l])) continue;//如果不在这个子集中就跳过

                     if(dis[i][l] == inf) {flag = false; break;}

                     tmp += k * dis[i][l];

                 }

                 if(flag) upmin(f[k + ][i | j], f[k][i] + tmp);

             }

         }

     }

     printf("%d\n", ans);

 }

 int main()

 {

 //    freopen("in.in", "r", stdin);

     pre();

     get();

     work();

 //    fclose(stdin);

     return ;

 }

巴特西

[NOIP2017]宝藏子集DP

最新文章

热门文章

巴特西

[NOIP2017]宝藏 子集DP

最新文章

热门文章

[NOIP2017]宝藏子集DP