洛谷P3959 [NOIP2017]宝藏

【题目描述】

参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 n 个深埋在地下的宝藏屋，也给出了这 n 个宝藏屋之间可供开发的 m 条道路和它们的长度。

小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远，也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路则相对容易很多。

小明的决心感动了考古挖掘的赞助商， 赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。

在此基础上， 小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏屋之间的道路无需再开发。

新开发一条道路的代价是：

这条道路的长度 × 从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋）。

请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代价最小，并输出这个最小值。

【输入格式】

第一行两个用空格分离的正整数 n 和 m，代表宝藏屋的个数和道路数。

接下来 m 行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏屋的编号（编号为 1~n），和这条道路的长度 v。

【输出格式】

输出共一行，一个正整数，表示最小的总代价。

【样例输入1】

4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1

【样例输出1】

4

【样例1提示】

【样例输入2】

4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 2

【样例输出2】

5

【样例2提示】

【数据规模】

对于 20%的数据：

保证输入是一棵树， 1≤n≤8， v≤5000 且所有的 v 都相等。

对于 40%的数据：

1≤n≤8， 0≤m≤1000， v≤5000 且所有的 v 都相等。

对于 70%的数据：

1≤n≤8， 0≤m≤1000， v≤ 5000

对于 100%的数据：

1≤n≤12， 0≤m≤1000， v≤ 500000

就把这道NOIP题当成回坑以后第一篇博吧（丢人

数据范围一眼状压DP，然而好像已经忘了DP怎么玩了

一顿胡乱撕烤，脑洞出一个常数巨大的解法。

F[a]表示联通状态为a的最优方案，G[a][]记录状态a的最优方案对应的每个结点深度，枚举边更新

注意到边数远超过完全图，可以预处理删掉无用边。

然而状态挂在了vector上常数过大，在洛谷上T了一个点，开O2可以A，假装自己过掉了（逃

（UPD6.15 突然发现代码放错了 噫呜呜噫）

 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 #include<cmath>
 #include<vector>
 using namespace std;
 typedef long long LL;
 int n,m;
 const int mxn=;
 const int N=<<;
 struct edge{
     int u,v,w;
     int next;
 }e[mxn<<];
 int hd[mxn],cnt=;
 void add_edge(int u,int v,int w){
     e[++cnt].u=u;e[cnt].v=v;e[cnt].w=w;
     e[cnt].next=hd[u];hd[u]=cnt;
     return;
 }
 int f[N];
 struct node{
     int dep[];
 };
 vector<node>g[N];
 //

 node tt,a;
 void solve(){
     int tmp=<<n;
     for(int i=;i<=n;i++){
         f[<<(i-)]=;
         tt.dep[i-]=;
         g[<<(i-)].push_back(tt);
         tt.dep[i-]=;
     }
     for(int i=;i<tmp;i++){
 //        printf("tmp:%d  %d\n",i,f[i]);
         for(int u=;u<n;u++){
             if( (i&(<<u)) ){
 //                printf(" u:%d\n",u);
                 for(int now=;now<g[i].size();now++){
 //                    printf("   now:%d\n",now);
                     for(int h=hd[u];h;h=e[h].next){

                         int v=e[h].v;
 //                        printf("   v:%d\n",v);
                         if(i&(<<v))continue;
 //                        printf("   v:%d\n",v);

                         int tar=i|(<<v);
 //                        printf("    tar:%d\n",tar);
                         if(f[tar] > f[i] + e[h].w*g[i][now].dep[u] ){
                             f[tar] = f[i] + e[h].w*g[i][now].dep[u];
                             a=g[i][now];
                             a.dep[v]=g[i][now].dep[u]+;
                             g[tar].clear();
                             g[tar].push_back(a);
                             a.dep[v]=;
                         }
                         else if(f[tar]== (f[i] + e[h].w*g[i][now].dep[u])){
                             a=g[i][now];
                             a.dep[v]=g[i][now].dep[u]+;
                             g[tar].push_back(a);
                             a.dep[v]=;
                         }
                     }
                 }
             }
         }
     }
     return;
 }
 int mp[][];
 int main(){
     int i,j,u,v,w;
     scanf("%d%d",&n,&m);
     memset(mp,0x3f,sizeof mp);
     for(i=;i<=m;i++){
         scanf("%d%d%d",&u,&v,&w);
         --u;--v;
         mp[u][v]=mp[v][u]=min(mp[u][v],w);
     }
     for(i=;i<n;i++)
         for(j=;j<n;j++)
             if(mp[i][j]<0x3f3f3f3f)
                 add_edge(i,j,mp[i][j]);
     memset(f,0x3f,sizeof(f));
     solve();
     printf("%d\n",f[(<<n)-]);
     return ;
 }

更好的解法是f[a][dep]记录联通状态为a，最深的点深度为dep的最优解，进行转移。