• P3959 [NOIP2017 提高组] 宝藏

    题目来源

    [NOIP2017 提高组] 宝藏 - 洛谷

    题目考点

    贪心，枚举，暴力，状态压缩，状压

    题目描述

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

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

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

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

    新开发一条道路的代价是 L×K。其中 L 代表这条道路的长度，K 代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋） 。

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

    输入格式

    第一行两个用空格分离的正整数 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

    输入 #2

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

    输出 #2

    5

    说明/提示

    【样例解释 11】

    小明选定让赞助商打通了 1 号宝藏屋。小明开发了道路 1→2，挖掘了 2 号宝藏。开发了道路 1→4，挖掘了 4 号宝藏。还开发了道路 4→3，挖掘了 3 号宝藏。

    工程总代价为 1×1+1×1+1×2=4。

    【样例解释 22】

    小明选定让赞助商打通了 11 号宝藏屋。小明开发了道路 1→2，挖掘了 2 号宝藏。开发了道路 1→3，挖掘了 3 号宝藏。还开发了道路 1→4，挖掘了 4 号宝藏。

    工程总代价为 1×1+3×1+1×1=5。

    【数据规模与约定】

    对于 20% 的数据： 保证输入是一棵树，1≤n≤8，v≤5×10^{3} 且所有的 vv 都相等。

    对于 40% 的数据： 1^30≤m≤10^{3}，0≤m≤10^{3}，v≤5×10^{3} 且所有的 vv 都相等。  

    对于 70% 的数据： 1≤n≤8，0≤m≤10^{3}，10^3v≤5×10^{3}。 

    对于 100% 的数据： 1≤n≤12，0≤m≤10^{3}，10^5v≤5×10^{5}。

     题解

    提供一篇题解里都没有写到的状压DP。

    看到数据范围就知道大概是个状压了。考虑一下怎么设计状态。

    看懂题意，题目的意思就是找一棵生成树，使得代价和最小。

    考虑在任意时刻，我们关心的只有我们已经把多少点加进生成树了，以及生成树的最大树高是多少。

    那么我们就设f_{s,i}为当前生成树已经包含集合S中的点，并且树高是i。

    那么状态转移方程就出来了：

    f_{s,i}=min{f_{S0,i-1}​+pay}，其中满足S_{0}是S的子集，通过S_{0}加边一定可以联结成S。pay是这次加边的花费。  

    那么怎么判断S_{0}​在转移中是否合法呢？我们设GS​是S能拓展到的边的集合，显然G是可以预处理出来的。 

    再考虑pay的计算。

    设ss=S xor S_{0}，即ss是在S但不在S_{0}中的元素。  

    这里pay的计算显然是对于每个ss中的元素取S_{0}中的元素向它连一条最短的边求和后×i。 

    考虑这么做为什么是对的。

    对于一个集合S和S_{0}，如果他们之间的边不是被S0​中最大深度的点连接成的，那么一定存在另一个S_{1}​，包含另一种连边的情况使得S1​包含除被最大深度点连接的点以外的所有点，那么通过S_{1}转移的答案就是最小值，一定是正确的。所以不会漏解。  

    现在来整理一下思路：

    1、预处理出对于每个点的集合所能拓展的点的集合。

    2、对于每个点显然把他作为通向地面的点的时候他的深度是0，集合是(1<

    3、枚举集合，对于每个集合的子集，通过GS​判断该子集是否合法，如果合法，枚举所有需要被连向的点的最小边权求和乘深度，作为答案。

    4、答案就是全集在1~n深度的最小值。

    下面考虑时间复杂度：

    首先考虑我们枚举集合的数量： 我们集合的枚举量显然是全集的子集的子集个数和。乍一看全集有2^{n}个子集，每个子集有n^{2}个子集。那么个数是O(4n)？事实上不是这样。考虑对于所有的的子集，他们的子集个数是O(2^{k})个，其中kk是子集的元素个数。那么对于大部分的子集，他们的元素个数k都不等于n。显然这个上界太松了。那么如何计算枚举量呢？考虑对于元素个数为x的子集，共有C_{n}^{x}​种方式。每个子集有2^{x}个子集，那么总的枚举量是C_{n}^{x} × 2^{x}。应用二项式定理，原式＝(2+1)^{n}=3^{n}。所以子集的枚举量是O(3^{n})。    

    对于每个集合最多有n个元素，每个元素枚举到它的边是O(n)的，所以这里的复杂度是O(n^{2})的。 

    那么总的复杂度是O(3^{n} × n^{2})。大概是七千万左右。考虑对于绝大部分集合跑不满n^{2}的上界，并且可以进行一些剪枝优化，最终可以通过本题 

    Code

    为了二进制运用方便，读入点的时候减一，所有的点从0编号到n-1。

    1. ​
    2. #include
    3. #include
    4. #define rg register
    5. #define ci const int
    6. #define cl const long long int
    7.  
    8. typedef long long int ll;
    9.  
    10. namespace IO {
    11. 	char buf[50];
    12. }
    13.  
    14. template<typename T>
    15. inline void qr(T &x) {
    16. 	char ch=getchar(),lst=' ';
    17. 	while(ch>'9'||ch<'0') lst=ch,ch=getchar();
    18. 	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    19. 	if (lst=='-') x=-x;
    20. }
    21.  
    22. template<typename T>
    23. inline void write(T x,const char aft,const bool pt) {
    24. 	if(x<0) {putchar('-');x=-x;}
    25. 	int top=0;
    26. 	do {
    27. 		IO::buf[++top]=x%10+'0';
    28. 		x/=10;
    29. 	} while(x);
    30. 	while(top) putchar(IO::buf[top--]);
    31. 	if(pt) putchar(aft);
    32. }
    33.  
    34. template <typename T>
    35. inline T mmax(const T a,const T b) {if(a>b) return a;return b;}
    36. template <typename T>
    37. inline T mmin(const T a,const T b) {if(areturn a;return b;}
    38. template <typename T>
    39. inline T mabs(const T a) {if(a<0) return -a;return a;}
    40.  
    41. template <typename T>
    42. inline void mswap(T &a,T &b) {T temp=a;a=b;b=temp;}
    43.  
    44.  
    45. const int maxn = 15;
    46. const int maxm = 1010;
    47. const int maxt = 1<
    48. const int INF = 0x3f3f3f3f;
    49.  
    50. int n,m,a,b,c,ans=INF;
    51. int frog[maxt][maxn],gorf[maxt],dis[maxn][maxn];
    52.  
    53. int main() {
    54. 	qr(n);qr(m);
    55. 	memset(dis,0x3f,sizeof dis);
    56. 	for(rg int i=1;i<=m;++i) {
    57. 		a=b=c=0;qr(a);qr(b);qr(c);--a;--b;
    58. 		dis[b][a]=dis[a][b]=mmin(dis[a][b],c);
    59. 	}
    60. 	memset(frog,0x3f,sizeof frog);
    61. 	int all=(1<-1;
    62. 	for(rg int i=1;i<=all;++i) {
    63. 		for(rg int j=0;jif(((1<
    64. 			dis[j][j]=0;
    65. 			for(rg int k=0;kif(dis[j][k]!=INF) {
    66. 				gorf[i]|=(1<
    67. 			}
    68. 		}
    69. 	}
    70. 	for(rg int i=0;i1<0]=0;
    71. 	for(rg int i=2;i<=all;++i) {
    72. 		for(rg int s0=i-1;s0;s0=(s0-1)&i) if((gorf[s0]|i) == gorf[s0]) {
    73. 			int _sum=0;
    74. 			int ss=s0^i;
    75. 			for(rg int k=0;kif((1<
    76. 				int _temp=INF;
    77. 				for(rg int h=0;hif((1<
    78. 					_temp=mmin(_temp,dis[h][k]);
    79. 				}
    80. 				_sum+=_temp;
    81. 			}
    82. 			for(rg int j=1;jif(frog[s0][j-1]!=INF) {
    83. 				frog[i][j]=mmin(frog[i][j],frog[s0][j-1]+_sum*j);
    84. 			}
    85. 		}
    86. 	}
    87. 	for(rg int i=0;immin(ans,frog[all][i]);
    88. 	write(ans,'\n',true);
    89. 	return 0;
    90. }
    91.  
    92. ​

    Summary

    1、n个元素的子集的子集数量是3^{n}

    2、在进行状态设计时可以考虑对于每个时刻需要知道的信息，以此设计维度

    3、预处理大法吼啊！

    和上次的相比 更改了两个笔误的地点。重新提交希望管理员给过。

  • 相关阅读:
    【低代码】为客户设计个性化方案：列表篇（客户自己调整排序对齐等）
    TextCNN 实现股票时间序列预测(TensorFlow2版)
    Linux三剑客：awk的实用案例
    -邻接点-
    Java设计模式之桥接模式
    《Linux从练气到飞升》No.30 深入理解 POSIX 信号量与生产消费模型
    一文搞懂穷举算法
    批量导入SQL Server中的建表、建存储过程和建调度作业的文件
    关于Linux学习中的诸多问题
    CSS基础语法
  • 原文地址：https://blog.csdn.net/You_are_hanson/article/details/126083453