网站开发涉及到缓存吗,重庆营销网站,南通网站排名服务,四川营销型网站建设公司P3959 [NOIP2017 提高组] 宝藏
题意:
额题意不好说#xff0c;就是n个点m个边#xff0c;选定一个点为根节点#xff0c;构造一个最小生成树#xff0c;边的权值为该该边起点到根节点之间的点的数量K#xff08;不含根节点#xff09; * 道路长度 1n12 0m就是n个点m个边选定一个点为根节点构造一个最小生成树边的权值为该该边起点到根节点之间的点的数量K不含根节点 * 道路长度 1n12 0m1e3 v5e5
题解:
参考题解 这数据范围暴力暴力暴力 不我们用状压dp来做 我们设dp[i][j]表示用到第i个元素当前连接状态为j的花费的最小值 这个式子没办法直接转移因为每个边的花费是不一样的即k是不一样的我们可以重新设计一个状态我们将k值理解为距离初始化点的层数如图 被涂蓝色的就是根节点k就是划分的层数 这样我们设dp[i][j]表示到第i层总共取了的点的状态为j 转移为 dp[i][j] min(dp[i-1][k]trans[k][j] * (i-1)) trans[k][j] * (i-1)就是题目说的距离 * K(题目中说的k) k是j的子集即有可能转移到j的状态 trans[k][j]表示从状态k转移到状态j的最小花费路径 这个子集意思就是sub就是S的子集 这个子集怎么求 直接求2^n必然不行会T有小技巧 由公式
for (int sub S; sub; sub (sub - 1) S) {// sub 为 S 的子集
}
证明过程 最终答案就是min(dp[i][2n-1]) 初始化dp[1][2(i-1)] 0 (i∈[1,n]) 我感觉代码很妙思路也很妙让我想是真写不出来 我详细说trans如何求 现在i是当前状态j是i的子状态我们现在要状态转移从j–i tempi ^ j,即要转移的点(因为 ^ 为不同为1) 然后我们开始枚举temp中存在的点k(从高位往低位)然后求从k到j的最短距离tmin把tmin加入到trans[j][i]中
代码
#includeiostream
#includecstdio
#includecstring
using namespace std;
long long read()
{long long x0,f1; char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
const int N122;
const int M1N;
int n,m,dis[N][N],trans[M][M],POW[N];
long long f[N][M];
int main()
{nread(),mread();memset(dis,0x3f,sizeof dis);for(int i1;im;i){int sread(),tread(),vread();if(dis[s][t]v)dis[s][t]dis[t][s]v;}for(int i0;i(1n);i)for(int ji;j!0;j(j-1)i){bool OKtrue;int tempi^j;//状态i与状态j的不同之处状态转移为j-i for(int kn-1;k0;k--){if((tempk)1)//说明点k是转移中增加的点即 j没有i有 {int tmin0x3f3f3f3f;for(int L1;Ln;L)if(1(j(L-1)))//如果状态j包含此点 ,求出L到k1的最短距离//if(((1(L-1))j)(1(L-1))) tminmin(tmin,dis[L][k1]);if(tmin0x3f3f3f3f)//如果此路无法走通 {OKfalse;break;}trans[j][i]tmin;/*相当于把j到i这段路拆分成了好几份 */ temp-(1k);}}if(OKfalse)trans[j][i]0x3f3f3f3f;}memset(f,0x3f,sizeof f);for(int i1;in;i)f[1][(1(i-1))]0;for(int i2;in;i)for(int j0;j(1n);j)for(int kj;k!0;k(k-1)j)//k为j的子状态也就是k是j的子集 if(trans[k][j]!0x3f3f3f3f)//说明可以从状态k到j f[i][j]min(f[i][j],f[i-1][k](i-1)*trans[k][j]);long long ans0x3f3f3f3f3f3f3f3fll;for(int i1;in;i)ansmin(ans,f[i][(1n)-1]);printf(%lld,ans);return 0;
}
