一开始看是插头dp，后来发现还有一个叫斯坦纳树的东西
什么叫斯坦纳树，就是使给定点连通开销和最小的树（可以包含多余的点）
到这张平面图上，我们不难想到用dp来解决，设f[x,y,S]表示连通集合为S，树根为点(x,y)的最小开销
不难得到两个方程式
f[x,y,S]=min(f[x,y,s']+f[x,y,S-s']-a[x,y]) S'是S的一个子集，相当于合并两个数
f[x,y,S]=min(f[x',y',S]+a[x,y]) (x',y')与(x,y)相邻
由于景点很少，我们显然可以用状压dp，初始f[景点坐标，景点状态]=0
第一个方程转移大家都会，第二个方程转移是没有明确转移顺序，只要转移起点，因此我们用spfa转移
所以总的处理转移，我们穷举连通状况，然后先用第一个方程转移，然后再用第二个方程转移
const dx:array[..] of longint=(,,,-);
dy:array[..] of longint=(,-,,);
inf=;
type node=record
x,y,k:longint;
end; var q:array[..] of node;
pre:array[..,..,..] of node;
f:array[..,..,..] of longint;
v:array[..,..] of boolean;
a:array[..,..] of longint;
t,h,r,k,i,j,s,n,m,x,y:longint; function make(i,j,k:longint):node;
begin
make.x:=i;
make.y:=j;
make.k:=k;
end; procedure spfa(k:longint);
var i,x,y,x0,y0:longint;
begin
while h<=r do
begin
x0:=q[h].x; y0:=q[h].y;
v[x0,y0]:=false;
for i:= to do
begin
x:=x0+dx[i];
y:=y0+dy[i];
if (x<) or (x>n) or (y<) or (y>m) then continue;
if f[x,y,k]>f[x0,y0,k]+a[x,y] then
begin
f[x,y,k]:=f[x0,y0,k]+a[x,y];
pre[x,y,k]:=make(x0,y0,k);
if not v[x,y] then
begin
v[x,y]:=true;
inc(r);
q[r].x:=x; q[r].y:=y;
end;
end;
end;
inc(h);
end;
end; procedure dfs(x,y,k:longint);
var m:node;
begin
v[x,y]:=true;
m:=pre[x,y,k];
if m.x= then exit;
dfs(m.x,m.y,m.k);
if (m.x=x) and (m.y=y) then dfs(m.x,m.y,k-m.k);
end; begin
readln(n,m);
for i:= to n do
for j:= to m do
for k:= to do
f[i,j,k]:=inf;
for i:= to n do
for j:= to m do
begin
read(a[i,j]);
if a[i,j]= then
begin
f[i,j, shl t]:=;
inc(t);
end;
end;
h:=;
r:=;
for k:= to shl t- do
begin
for i:= to n do
for j:= to m do
begin
s:=k and (k-);
while s<> do //穷举子集
begin
if f[i,j,k]>f[i,j,s]+f[i,j,k-s]-a[i,j] then
begin
f[i,j,k]:=f[i,j,s]+f[i,j,k-s]-a[i,j];
pre[i,j,k]:=make(i,j,s); //记录从哪转移来的
end;
s:=k and (s-);
end;
if f[i,j,k]<inf then
begin
v[i,j]:=true;
inc(r);
q[r].x:=i; q[r].y:=j;
end;
end;
spfa(k);
h:=;
r:=;
end;
for i:= to n do
for j:= to m do
if a[i,j]= then
begin
x:=i;
y:=j;
break;
end; writeln(f[x,y, shl t-]);
dfs(x,y, shl t-);
for i:= to n do
begin
for j:= to m do
if a[i,j]= then write('x')
else if v[i,j] then write('o')
else write('_');
writeln;
end;
end.
随机推荐
-
利用CSS背景颜色属性使父级div背景透明同时避免子级标签透明。
实现背景色透明效果的代码 实现各个浏览器中具备良好的透明特性的效果,IE中使用私有滤镜filter,高端浏览器使用CSS3中的rgba属性. 输入十六进制的颜色值以及透明度,自动在IE的过渡滤镜以及C ...
-
学习ios【2】Objective-C 数字和字符串
一 数字 1.使用Foundation.h可以直接导入所有的头文件. 在XCode中,想查看某个方法帮助,可以将光标放在方法上,按住option键同时单击即可. 官方文档:https://develo ...
-
Google V8编程详解（四）Context
http://blog.csdn.net/feiyinzilgd/article/details/8266780 上一章,比较略提了下V8的Context.本章将详细的讲解下Context的概念以及用 ...
-
json对象的解析
json对象数据: { "status": "200", "code": "", "msg": &q ...
-
hnu Dirichlet&#39;s Theorem
/* 求ax+b x属于区间[L,R];范围内素数的个数. a*R+b<=10^12 ; R-L+1<=10^6 枚举,超时. 1.如果GCD(a,b)>1 那么a+b 2*a+b ...
-
【转】MessageBox
MessageBox对话框是比较常用的一个信息对话框,其不仅能够定义显示的信息内容.信息提示图标,而且可以定义按钮组合及对话框的标题,是一个功能齐全的信息对话框. 1.函数原型及参数 function ...
-
lightoj 1015
水题,统计大于0的和. #include<cstdio> int main(){ int t, n, tmp; scanf("%d", &t); for(int ...
-
c语言中的#ifndef、#def、#endif等宏是什么意思
#ifndef.(或者#ifndef).#def.#endif等宏这几个宏是为了进行条件编译.一般情况下,源程序中所有的行都参加编译.但是有时希望对其中一部分内容只在满足一定条件才进行编译,也就是对一 ...
-
Drools学习笔记-01-在eclipse indgo集成Drools5.5
1.1.条件 Drools它是一个基于Java开源规则引擎.因此,使用Drools以及前需要安装在开发机器JDK周边环境,Drools5.5需要JDK版本号的1.5或者更多. 1.2.开发环境搭建 大 ...
-
Openlayer3之绚丽的界面框架-Materialize
一群做C++的老伙计搞前端开发,徒手写html和css应该会折寿..在网上找了半天,Materialize算是用起来很方便的一款前端界面框架.Google的Material Design看起来感觉还是 ...