NOIP2017D2T2 | 宝藏

Portal

观察题目,12 个顶点,1000 条边,显然有很多重边(显然是状压 DP)。所以在输入时不断取最短边,最后边数不超过 122 条。由于题目求的是一个花费最小的生成树,并不关心从以哪个点为根,显然对于一棵生成树,取不同的点为根只会有深度的差别,在输出时找出所有深度中花费最小的即可,而不必枚举根节点。因为有 12 个顶点,显然状态有一维应为状态压缩的被探索过的顶点。

接下来可以考虑转移,首先枚举一个目标状态,显然如果要从它的一个子集转移到该状态,每次都应该从子集中深度最大的点向它的补集中连边,若不是从深度最大的点连边,则一定存在另一个更优的子集,故不会漏解。可以直接写出状态转移方程:

fA,d=min{fB,d1+c}(BA)f_{A,d}=\min {f_{B,d-1}+c} (B\subset A)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <cstring>
#include <algorithm>
int main() {
const int N=13,inf=0x3f3f3f3f;
int n,m,ed,ans=inf,g[N][N],ext[1<<N]={},f[1<<N][N];
memset(g,0x3f,sizeof(g));memset(f,0x3f,sizeof(f));
scanf("%d%d",&n,&m);ed=1<<n;
for(int i=0,u,v,w;i<m;++i)
scanf("%d%d%d",&u,&v,&w),g[--u][--v]=g[v][u]=std::min(g[u][v],w);
for(int i=0;i<n;++i) g[i][i]=f[1<<i][0]=0;
for(int i=1;i<ed;++i)
for(int j=0;j<n;++j) if(i&(1<<j))
for(int k=0;k<n;++k) if(g[j][k]!=inf) ext[i]|=(1<<k);
for(int i=2;i<ed;++i)
for(int sub=i-1,sum,flip;sub;sub=(sub-1)&i)
if((ext[sub]&i)==i) {
sum=0;flip=sub^i;
for(int v=0,tmp;v<n;++v) if(flip&(1<<v)) {
tmp=inf;
for(int u=0;u<n;++u) if(sub&(1<<u)) tmp=std::min(tmp,g[u][v]);
sum+=tmp;
}
for(int j=1;j<n;++j) if(f[sub][j-1]!=inf)
f[i][j]=std::min(1LL*f[i][j],f[sub][j-1]+1LL*sum*j);
}
for(int i=0;i<n;++i) ans=std::min(ans,f[ed-1][i]);
printf("%d",ans);
return 0;
}

Download

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

题解 OI

评论

您需要成为穿墙的邪仙以加载 Disqus。