Luogu P3577 [POI2014]TUR-Tourism
2024-10-19 00:25:45
Luogu P3577 [POI2014]TUR-Tourism
题目大意:给出一张\(n\)个点,\(m\)条边的无向图,保证任意两点之间没有点数超过\(10\)的简单路径。选择第\(i\)个点要支付\(C_i\)的代价,要求用最小的代价使得每个点被选择或者与一个被选择的点相邻。
\(n\leq 20000,m\leq 25000,C_i\leq 1000\)。
可以发现,如果原问题是在树上的话就很简单。所以我们先建出\(dfs\)树。因为这是无向图,所以所有的非树边都是返祖边。由题目中那个神奇的性质,我们可以知道,这棵树的深度不超过\(10\)。
于是我们可以状压。设\(f_{i,S}\)表示第\(i\)个点,其祖先的状态为\(S\)的最小代价。
状压的状态有三种:
0:没有选择且没被覆盖
1.没有选择但被覆盖了
2.选择了
转移就有点厉害,据说是泛化背包。
当由\(fa_v\)递归到\(v\)的时候,\(dfs\)序比\(v\)小的点中除了\(v\)到根这条链上都已经被覆盖了。然后将\(f_{fa_v,S}\)的\(DP\)值继承给\(f_{v,S'}\)。继承的时候讨论是否选择\(v\)得到\(S'\)。
一直递归到底后回溯,\(f_{fa_v,S}=\min\{f_{v,S+3^{dep_v}},f_{v,S+2*3^{dep_v}}\}\)。接着递归下一个儿子。这个\(DP\)是按\(dfs\)序来的,当一个点出栈了过后,保证这个点已经被覆盖,无需再考虑。
\(DP\)的结果就是\(\min\{f_{root,1},f_{root,2}\}\)。将每个联通块的答案加起来就行了。
代码:
#include<bits/stdc++.h>
#define ll long long
#define N 20005
#define M 25005
using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
int n,m,C[N];
struct road {int to,nxt;}s[M<<1];
int h[N],cnt;
void add(int i,int j) {s[++cnt]=(road) {j,h[i]};h[i]=cnt;}
int pw[15];
bool vis[N];
int fa[N],dep[N];
int f[12][60000];
void dfs(int v) {
vis[v]=1;
if(dep[v]==0) {
f[0][0]=0;
f[0][1]=1e9;
f[0][2]=C[v];
} else {
for(int i=h[v];i;i=s[i].nxt) {
int to=s[i].to;
if(vis[to]) fa[v]|=1<<dep[to];
}
for(int S=0;S<pw[dep[v]+1];S++) f[dep[v]][S]=1e9;
for(int S=0;S<pw[dep[v]];S++) {
if(f[dep[v]-1][S]>=1e9) continue ;
bool flag=0;
for(int i=0;i<dep[v];i++) if((fa[v]>>i&1)&&S/pw[i]%3==2) flag=1;
f[dep[v]][S+flag*pw[dep[v]]]=min(f[dep[v]][S+flag*pw[dep[v]]],f[dep[v]-1][S]);
int T=S+2*pw[dep[v]];
for(int i=0;i<dep[v];i++) if((fa[v]>>i&1)&&S/pw[i]%3==0) T+=pw[i];
f[dep[v]][T]=min(f[dep[v]][T],f[dep[v]-1][S]+C[v]);
}
}
int flag=0;
for(int i=h[v];i;i=s[i].nxt) {
int to=s[i].to;
if(vis[to]) continue ;
dep[to]=dep[v]+1;
dfs(to);
for(int S=0;S<pw[dep[v]+1];S++) {
f[dep[v]][S]=min(f[dep[to]][S+pw[dep[to]]],f[dep[to]][S+2*pw[dep[to]]]);
}
}
}
int main() {
pw[0]=1;
for(int i=1;i<=10;i++) pw[i]=pw[i-1]*3;
n=Get(),m=Get();
for(int i=1;i<=n;i++) C[i]=Get();
for(int i=1;i<=m;i++) {
int a=Get(),b=Get();
add(a,b),add(b,a);
}
int ans=0;
for(int i=1;i<=n;i++) {
if(vis[i]) continue ;
dfs(i);
ans+=min(f[0][1],f[0][2]);
}
cout<<ans;
return 0;
}
最新文章
- JavaScript学习笔记(四)——jQuery插件开发与发布
- gulp(一)
- [fortify] open redirect漏洞
- 修改placeholder提示内容的颜色以及文本框输入文字内容的颜色
- mysql 权限设置
- RESTful API 简书
- springMVC入门配置及helloworld实例
- 修改ElementUI源码实践
- 克服";水土不服";,融云助攻小象直播杀破";出海重围";
- 《Linux就该这么学》第十五天课程
- c++入门之再话命名空间的意义
- c# 正则匹配对称括号
- 求计算两个时间的差(DateTime类和TimeSpan类)
- JDK1.5新特性,基础类库篇,格式化类(Formatter)用法
- tomcat 启动自动加载外部项目
- [linux]df 磁盘100%Used告警,du显示目录状态良好的故障排查
- Mac OS X 编译android内核 error: elf.h: No such file or directory 的解决方法
- RequireJs学习笔记之Define a Module
- openresty安装配置 Ubuntu下
- POJ 2082 Terrible Sets(栈)