luogu3959 宝藏

luogu3959 宝藏

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

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

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

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

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

\mathrm{L} \times \mathrm{K}

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 说明

【样例解释1】

小明选定让赞助商打通了 1 号宝藏屋。小明开发了道路

1 \to 2

1→2，挖掘了 2 号宝 藏。开发了道路

1 \to 4

1→4，挖掘了 4 号宝藏。还开发了道路

4 \to 3

4→3，挖掘了 3 号宝 藏。工程总代价为：

1 \times 1 + 1 \times 1 + 1 \times 2 = 4

1×1+1×1+1×2=4

【样例解释2】

小明选定让赞助商打通了 1 号宝藏屋。小明开发了道路

1 \to 2

1→2，挖掘了 2 号宝 藏。开发了道路

1 \to 3

1→3，挖掘了 3 号宝藏。还开发了道路

1 \to 4

1→4，挖掘了 4 号宝 藏。工程总代价为：

1 \times 1 + 3 \times 1 + 1 \times 1 = 5

1×1+3×1+1×1=5

【数据规模与约定】

对于 20%的数据： 保证输入是一棵树，

1 \le n \le 8

1≤n≤8，

v \le 5000

v≤5000 且所有的 v 都相等。

对于 40%的数据：

1 \le n \le 8

1≤n≤8，

0 \le m \le 1000

0≤m≤1000，

v \le 5000

v≤5000 且所有的 v 都相等。

对于 70%的数据：

1 \le n \le 8

1≤n≤8，

0 \le m \le 1000

0≤m≤1000，

v \le 5000

v≤5000

对于 100%的数据：

1 \le n \le 12

1≤n≤12，

0 \le m \le 1000

0≤m≤1000，

v \le 500000

v≤500000

复杂度2^n*n^4

不知道这个方法是否正确

设f[s][i] 当前我有s状态的点已经遍历了 然后我现在处于i点 我的最优答案是多少

同时设置step[s][i]表示连接了这些点 在这个状态下 我 处于i号节点 我距离根的深度是多少

这样的话 相当于我对于step数组相当于记录了每个树的形态 然后直接转移即可 假如我这些都确定了 可以dp一下 则我每次从我当前已经连接的点中去枚举一个继续连接的点 然后再枚举 一个可以连接的终点 算一下代价转移即可 然后对于step数组 只有我即将转移的状态更优的时候我才可以去更新step相当于贪心的选择最优方案 从局部扩展到全局

#include#include#include#define inf 0x3f3f3f3fusing namespace std;int fa[1<<13],dp[1<<13],n,m,bin[20],mp[20][20];/*inline int find(int s,int need){ int s1=bin[n]-1;s1^=bin[need]; if((s1^s)==bin[n]-1) return 1; int cnt=find(fa[s],need); return cnt+1;}*/int step[1<<13][20];int main(){ // freopen("treasure.in","r",stdin); // freopen("treasure.out","w",stdout); scanf("%d%d",&n,&m);memset(mp,0x3f,sizeof(mp)); for (int i=1;i<=m;++i){ int x,y,z;scanf("%d%d%d",&x,&y,&z);x-=1;y-=1; mp[x][y]=min(mp[x][y],z);mp[y][x]=min(mp[y][x],z); } for (int i=0;i<=n;++i) bin[i]=1<

这个应该就是官方做法了 设f[dep][s][s1] 第一维为我枚举的树的深度 s表示我现在已经连接的点 然后s1 表示当前我这一层连接的点

然后我需要提前预处理出两个s1 s2状态之间连边的最小值

然后每次枚举深度 去转移即可

怎么预处理 我首先 预处理每个点 连接每种情况的最小情况 在我的程序里是Pre数组

然后通过Pre数组转移出我想要的st数组表示两种状态连接起来的最小代价是多少

复杂度:4^n*n

#include#include#define inf 0x3f3f3f3finline int min(int x,int y){return x'9'){if (ch=='-') f=-1;ch=gc();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}int f[2][4100][4100],st[4100][4100],mp[20][20],pre[13][4100],bin[20],n,m;int main(){// freopen("3959.in","r",stdin); n=read();m=read();memset(mp,0x3f,sizeof(mp));memset(pre,0x3f,sizeof(pre));memset(st,0x3f,sizeof(st)); if (m==0){printf("0");return 0;} for (int i=1;i<=m;++i){ int x=read(),y=read();int tmp=read();x--;y--; mp[x][y]=mp[y][x]=min(mp[x][y],tmp); } for (int i=0;i<=n;++i) bin[i]=1<

这种方法 是减少了枚举最后一层的情况 因为 这样可能产生 不是最后一层连接的后面的点 然后

但是因为从前面往后面连接的点 如果不是从最后一层开始转移那么一定不是最优的方案

所以可以减少最后一个枚举最后一层的状态

3^n*n

#include#include#define inf 0x3f3f3f3finline int min(int x,int y){return x'9'){if (ch=='-') f=-1;ch=gc();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}int f[12][4100],st[4100][4100],mp[20][20],pre[13][4100],bin[20],n,m;int main(){ //freopen("treasure.in","r",stdin); n=read();m=read();memset(mp,0x3f,sizeof(mp));memset(pre,0x3f,sizeof(pre));memset(st,0x3f,sizeof(st)); if(m==0) {printf("0");return 0;} for (int i=1;i<=m;++i){ int x=read(),y=read();int tmp=read();x--;y--; mp[x][y]=mp[y][x]=min(mp[x][y],tmp); } for (int i=0;i<=n;++i) bin[i]=1<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。