建设社团网站的可行性分析,如何做com的网站,混合式教学财务管理网站建设,山西城乡建设厅网站首页题目链接
[NOIP2017 提高组] 宝藏
题目描述
参与考古挖掘的小明得到了一份藏宝图#xff0c;藏宝图上标出了 n n n 个深埋在地下的宝藏屋#xff0c; 也给出了这 n n n 个宝藏屋之间可供开发的 m m m 条道路和它们的长度。
小明决心亲自前往挖掘所有宝藏屋中的宝藏。但…题目链接
[NOIP2017 提高组] 宝藏
题目描述
参与考古挖掘的小明得到了一份藏宝图藏宝图上标出了 n n n 个深埋在地下的宝藏屋 也给出了这 n n n 个宝藏屋之间可供开发的 m m m 条道路和它们的长度。
小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是每个宝藏屋距离地面都很远也就是说从地面打通一条到某个宝藏屋的道路是很困难的而开发宝藏屋之间的道路则相对容易很多。
小明的决心感动了考古挖掘的赞助商赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道通往哪个宝藏屋则由小明来决定。
在此基础上小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。另外小明不想开发无用道路即两个已经被挖掘过的宝藏屋之间的道路无需再开发。
新开发一条道路的代价是 L × K \mathrm{L} \times \mathrm{K} L×K。其中 L L L 代表这条道路的长度 K K K 代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋 。
请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路使得工程总代价最小并输出这个最小值。
输入格式
第一行两个用空格分离的正整数 n , m n,m n,m代表宝藏屋的个数和道路数。
接下来 m m m 行每行三个用空格分离的正整数分别是由一条道路连接的两个宝藏屋的编号编号为 1 − n 1-n 1−n和这条道路的长度 v v v。
输出格式
一个正整数表示最小的总代价。
样例 #1
样例输入 #1
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1样例输出 #1
4样例 #2
样例输入 #2
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 2样例输出 #2
5提示 【样例解释 1 1 1】
小明选定让赞助商打通了 1 1 1 号宝藏屋。小明开发了道路 1 → 2 1 \to 2 1→2挖掘了 2 2 2 号宝藏。开发了道路 1 → 4 1 \to 4 1→4挖掘了 4 4 4 号宝藏。还开发了道路 4 → 3 4 \to 3 4→3挖掘了 3 3 3 号宝藏。
工程总代价为 1 × 1 1 × 1 1 × 2 4 1 \times 1 1 \times 1 1 \times 2 4 1×11×11×24。
【样例解释 2 2 2】
小明选定让赞助商打通了 1 1 1 号宝藏屋。小明开发了道路 1 → 2 1 \to 2 1→2挖掘了 2 2 2 号宝藏。开发了道路 1 → 3 1 \to 3 1→3挖掘了 3 3 3 号宝藏。还开发了道路 1 → 4 1 \to 4 1→4挖掘了 4 4 4 号宝藏。
工程总代价为 1 × 1 3 × 1 1 × 1 5 1 \times 1 3 \times 1 1 \times 1 5 1×13×11×15。
【数据规模与约定】
对于 20 % 20\% 20% 的数据 保证输入是一棵树 1 ≤ n ≤ 8 1 \le n \le 8 1≤n≤8 v ≤ 5 × 1 0 3 v \le 5\times 10^3 v≤5×103 且所有的 v v v 都相等。
对于 40 % 40\% 40% 的数据 1 ≤ n ≤ 8 1 \le n \le 8 1≤n≤8 0 ≤ m ≤ 1 0 3 0 \le m \le 10^3 0≤m≤103 v ≤ 5 × 1 0 3 v \le 5\times 10^3 v≤5×103 且所有的 v v v 都相等。
对于 70 % 70\% 70% 的数据 1 ≤ n ≤ 8 1 \le n \le 8 1≤n≤8 0 ≤ m ≤ 1 0 3 0 \le m \le 10^3 0≤m≤103 v ≤ 5 × 1 0 3 v \le 5\times 10^3 v≤5×103。
对于 100 % 100\% 100% 的数据 1 ≤ n ≤ 12 1 \le n \le 12 1≤n≤12 0 ≤ m ≤ 1 0 3 0 \le m \le 10^3 0≤m≤103 v ≤ 5 × 1 0 5 v \le 5\times 10^5 v≤5×105。
算法思想
根据题目描述小明需要考虑如何开凿宝藏屋之间的道路并且两个已经被挖掘过的宝藏屋之间的道路无需再开发也就是说题目求的是一棵生成树使得代价和最小。
由于开发一条道路的代价与道路的长度 L L L和从起点到宝藏屋所经过的宝藏屋的数量即宝藏屋的深度 K K K有关因此不能使用最小生成树的算法进行计算。
考虑到结点数 n n n的范围较小 1 ≤ n ≤ 12 1 \le n \le 12 1≤n≤12考虑使用状态压缩动态规划解决。
状态表示
用 S S S表示当前生成树的状态其二进制位上的 0 0 0和 1 1 1表示是否包含相应的宝藏屋。例如当有 0 、 1 、 2 、 3 、 4 0、1、2、3、4 0、1、2、3、4一共 5 5 5个宝藏屋时目前生成树已经包含了 0 、 3 、 4 0、3、4 0、3、4那么 s t a t e ( 11001 ) 2 state(11001)_2 state(11001)2。 s t a t e state state的范围从 0 ∼ 2 n − 1 0\sim 2^n-1 0∼2n−1。
状态除了跟当前生成树的情况有关还与树的深度有关用 i i i表示当前生成树的深度其中起点的深度为 0 0 0。
因此 f [ s t a t e ] [ i ] f[state][i] f[state][i]表示当前生成树状态为 s t a t e state state、并且树的深度为 i i i时工程总代价的最小值。
最终结果为包含所有宝藏屋时对于不同深度的生成树取最小值即 m i n { f [ 2 n − 1 ] [ i ] } min\{f[2^n-1][i]\} min{f[2n−1][i]}其中 0 ≤ i n 0\le in 0≤in。
状态计算
状态转移
要计算当前状态 f [ s t a t e ] [ i ] f[state][i] f[state][i]从最后一步分析即从第 i − 1 i-1 i−1层可以转移到第 i i i层
不妨设第 i i i层点集宝藏屋的状态为 s s s s s s是状态 s t a t e state state的一个子集如果前 i − 1 i-1 i−1层的点集的状态为 t t t那么 t s t a t e ⊕ s t state\oplus s tstate⊕s异或运算 x o r xor xor
因此 f [ s t a t e ] [ i ] m i n { f [ t ] [ i − 1 ] c o s t } f[state][i] min\{f[t][i-1]cost\} f[state][i]min{f[t][i−1]cost}
计算代价
其中 c o s t cost cost表示第 i i i层所有点宝藏屋到第 i − 1 i-1 i−1层的最小代价。那么 c o s t L × K cost L\times K costL×K其中 L L L表示第 i i i层所有点到第 i − 1 i-1 i−1层的长度之和 K K K代表从起点到第 i i i的深度。
为了能够快速计算 L L L可以预处理得到任一点到所有集合的最小长度不妨设 g [ i ] [ s t a t e ] g[i][state] g[i][state]表示点 i i i到点集 s t a t e state state的最小长度。那么 g [ i ] [ s t a t e ] g[i][state] g[i][state]等于点 i i i到点集 s t a t e state state中任意一点的最短距离。
算法流程
枚举所有要计算的点集 s t a t e state state在计算当前状态 f [ s t a t e ] [ i ] f[state][i] f[state][i]时
要枚举 s t a t e state state的所有子集即第 i i i层的点集状态 s s s 计算出第 i i i层的所有点到第 i − 1 i-1 i−1层的最小长度之和 L L L然后再枚举深度 i i i计算 f [ s t a t e ] [ i ] f[state][i] f[state][i]
初始状态
求的是工程总代价最小值因此 f f f数组应初始化尽可能大可以打通任意一个宝藏屋到地面的通道到因此对于任意一点 i i i在生成树中只包含该点、且深度为 0 0 0时其最小值应该为 0 0 0即 f [ 1 i ] [ 0 ] 0 f[1i][0]0 f[1i][0]0
时间复杂度
时间复杂度包含两部分
预处理 g [ i ] [ s t a t e ] g[i][state] g[i][state]的时间复杂度为 O ( n 2 × 2 n ) O(n^2\times2^n) O(n2×2n) 状态数为 n × 2 n n\times2^n n×2n计算过程中需要枚举任意集合 s t a t e state state中任意点时间复杂度 O ( n ) O(n) O(n) 计算状态 f [ s t a t e ] [ i ] f[state][i] f[state][i]的时间复杂度为 O ( n 2 × 3 n ) O(n^2\times3^n) O(n2×3n) 计算过程中需要枚举集合的所有子集。考虑对于元素个数为 k k k的子集一共有 C n k C_n^k Cnk种情况每个子集有 2 k 2^k 2k个子集那么需要枚举的次数为 ∑ k 0 n C n k × 2 k \sum_{k0}^nC_n^k\times2^k ∑k0nCnk×2k。利用二项式定理 ∑ k 0 n C n k × 2 k ( 1 2 ) n 3 n \sum_{k0}^nC_n^k\times2^k(12)^n3^n ∑k0nCnk×2k(12)n3n。对于每个子集需要 n 2 n^2 n2次计算来算出剩余点到子集中的最小长度。 二项式定理 ( x y ) n C n 0 x n y 0 C n 1 x n − 1 y 1 C n 2 x ( n − 2 ) y 2 . . . C n n − 1 x 1 y n − 1 C n n x 0 y n (xy)^nC_n^0x^ny^0C_n^1x^{n-1}y^1C_n^2x^(n-2)y^2...C_n^{n-1}x^1y^{n-1}C_n^nx^0y^n (xy)nCn0xny0Cn1xn−1y1Cn2x(n−2)y2...Cnn−1x1yn−1Cnnx0yn 代码实现
#include iostream
#include cstring
using namespace std;const int N 12, M 1 N, INF 0x3f3f3f3f;
//g[i][state]表示点i到集合state的最小长度
int w[N][N], g[N][M];
//f[state][i]表示当前生成树状态为state、并且树的深度为i时工程总代价的最小值
int f[M][N];
int main()
{int n, m;cin n m;memset(w, 0x3f, sizeof w);while(m --){int a, b, c;cin a b c;//点的编号从0开始以便处理点集a --, b --;//有重边所以取最小值w[a][b] w[b][a] min(w[a][b], c);}//预处理任一点到所有集合的最小长度memset(g, 0x3f, sizeof g);for(int i 0; i n; i )for(int state 0; state 1 n; state )//枚举state中的点for(int k 0; k n; k )if(state k 1)//更新i到集合state长度的最小值g[i][state] min(g[i][state], w[i][k]); //初始状态memset(f, 0x3f, sizeof f);//以i点为起点到达深度0的最小代价为0for(int i 0; i n; i ) f[1 i][0] 0;//状态计算for(int state 1; state 1 n; state ){//枚举state的子集sfor(int s state - 1 state; s ! 0; s s - 1 state){//t表示前i-1层的点集状态int t state ^ s, L 0;//枚举第i层所有点计算第i层的所有点到第i-1层的最小长度之和Lfor(int k 0; k n; k ){if(s k 1) //点k在第i层的集合中{L g[k][t]; //累加最后一层所有点到上一层的长度if(L INF) break; //点k到不了第i-1层的所有点}}if(L INF) continue; //子集s中存在点无法到达第i-1层//枚举深度计算当前状态f[state][i]for(int i 1; i n; i )f[state][i] min(f[state][i], f[t][i - 1] L * i);}}//结果为包含所有宝藏屋时对于不同深度的生成树取最小值int ans INF;for(int i 0; i n; i )ans min(ans, f[(1 n) - 1][i]);cout ans;return 0;
}
