【NOIP17 D2T2】宝藏

Source and Judge

NOIP2017 提高组 D2T2
Loj2318
Luogu3959

Problem

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

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

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

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

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

L×K

L代表这条道路的长度,K代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量(包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋) 。

请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路,使得工程总代 价最小,并输出这个最小值。
【Input】
第一行两个用空格分离的正整数 n,m ,代表宝藏屋的个数和道路数。
接下来 m 行,每行三个用空格分离的正整数,分别是由一条道路连接的两个宝藏 屋的编号(编号为 1−n ),和这条道路的长度 v 。
【Output】
一个正整数,表示最小的总代价。
【Limited conditions】
1≤n≤12, 0≤m≤1000, v≤500000
【Sample input 1】
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1
【Sample output 1】
4
【Sample input 2】
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 2
【Sample output 2】
5
【Sample explanation】

Record

3h
去年比赛的时候想了半天,没想出什么数据能卡贪心地最小生成树
然后就被卡到了45分

Analysis

请先思考后再展开

rose曾经提出的做法:
用$f[S][now][dep]$表示当点的状态为S,现在在now且深度为dep时的最优结果
那么把不同种起点方式塞进去之后,就可以转移
复杂度为$2^n \times n \times n \times n$

看起来没有任何问题,对吧?
我一开始也是这样认为的,就是一直心里有种别扭的感觉
后来想半天终于发现,因为把其他点的信息舍去了,再也不能从别的点出发转移了


正解是状压dp
这次的状压灰常独特呢
反正我是没见过……

设$f[dep][S]$表示当前的状态是S,最大深度是dep时的最小代价
然后枚举每个状态进行转移的时候,每次直接添加一个点集,直接全部作为新的一层
至于代价,考虑到题目的特殊性,树的结构具体如何无关紧要,只和每个节点的深度有关
既然如此,只要预处理出每个节点添加到一个点集中的代价,再预处理成点集即可


然后让我们分析一下复杂度
大致上=dp时枚举dep的时间 × 所有状态转移时枚举【补集的子集】的时间花费
那么其实枚举【补集的子集】就是枚举子集

如果直接从循环量看,一定是比$O(2^n \times 2^n)=2亿$少的
当然按照akc在省选后的教训,这个也可能跑出灰常多的分数
但这个时间到底是多少呢?

因为这东西是和rose一起xjb想出来的,不一定严谨
而且好像和别的大佬看起来不一样?
考虑按照【含0数量】分类
$2^12 \times C_12^0$
$2^11 \times C_12^1$
……
$2^6 \times C_12^6$
……
$2^1 \times C_12^11$
$2^0 \times C_12^12$

那么最大的显然是$2^6 \times C_12^6<=60000$
那么它们的总和$< 60000*12=720000$
所以总复杂度就是8640000

UP 晚上:
问了问师兄,得出了和网上大佬相同的结论
对于这种连续的枚举子集问题,复杂度其实是$O(n^3)$
对于每个数位,只有3种情况,原本是0,原本是1枚举子集成0,原本是1枚举子集成1

Code

请先思考后再展开
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=110000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
ull mymin(ull x,ull y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int bin[15];
const int MAXS=1<<12;
int n,maxs;
int dis[15][15];
int v[15];//原本位置
ull value[15][MAXS];//点=>集
int cost[MAXS][MAXS];//集=>集
void pre()//3^n*n
{
memset(value,63,sizeof value);
for(int s=0;s<=maxs;s++)
{
for(int i=0;i<=n-1;i++) if(s&bin[i])
for(int j=0;j<=n-1;j++) if( (s&bin[j])==0 )
value[j][s]=mymin(value[j][s],dis[i][j]);
for(int s2=(maxs-s);s2>0;s2=(s2-1)&(maxs-s))//枚举补集的子集
for(int i=0;i<=n-1;i++)
if(s2&bin[i]) cost[s2][s]+=value[i][s];
}
}
ull f[15][MAXS];
void dp()//n*3^n
{
memset(f,63,sizeof f);
for(int i=0;i<=n-1;i++) f[1][bin[i]]=0;
for(int dep=1;dep<=n;dep++)
for(int s=1;s<=maxs;s++)//debug 不能是0
for(int s2=(maxs-s);s2>0;s2=(s2-1)&(maxs-s))//枚举补集的子集
f[dep+1][s|s2]=mymin(f[dep+1][s|s2],f[dep][s]+(ull)cost[s2][s]*dep);
}
int main()
{
bin[0]=1;for(int i=1;i<15;i++) bin[i]=bin[i-1]<<1;
int m;scanf("%d%d",&n,&m);
memset(dis,63,sizeof dis);
for(int i=1;i<=m;i++)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
x--;y--;
if(dis[x][y]>c) dis[x][y]=dis[y][x]=c;
}
maxs=bin[n]-1;
pre();
dp();
ull ans=INF;
for(int dep=1;dep<=n;dep++) ans=mymin(ans,f[dep][maxs]);
printf("%lld",ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/301d.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%