注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2595][Wc2008]游览计划  

2015-04-21 10:53:50|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2595: [Wc2008]游览计划

斯坦纳树模板

#include<cstdio>
#include<cstdlib>
#include<queue>
#include<algorithm>
using namespace std;
const int MAX = 1E9+7;
int scan(){int i=0;scanf("%d",&i);return i;}
const int N = 11;
const int TN = 1<<10;
int n,m,data[N][N],cot,two[100];
int from[N][N][TN],d[N][N][TN],st[N][N];
short out[N][N],in[N][N][TN];
int pack(int x,int y,int zh){return zh + y*10000 + x*100000;}
int get(int val,int &x,int &y,int &zh){
zh = val%10000;
val/=10000;
y = val%10;x = val/10;
}
short dir[5][2] = {{0,-1},{0,1},{-1,0},{1,0}};
queue<int>dui;
void spfa(){
int x,y,zh,X,Y,ZH,now;
while(!dui.empty()){
get(now=dui.front(),x,y,zh);
dui.pop();
for(int i=0;i<4;i++){
X = x + dir[i][0];
Y = y + dir[i][1];
if(!(0<=X&&X<n && 0<=Y&&Y<m))continue;
ZH = zh|st[X][Y];
if(d[x][y][zh] + data[X][Y] < d[X][Y][ZH]){
d[X][Y][ZH] = d[x][y][zh] + data[X][Y];
from[X][Y][ZH] = now;
if(!in[X][Y][ZH] && zh==ZH){
in[X][Y][ZH] = 1;
dui.push(pack(X,Y,ZH));
}
}
}
in[x][y][zh]=0;
}
}
void getans(int x,int y,int zh){
out[x][y] = 1;
int t = from[x][y][zh],X,Y,ZH;
if(!t)return;
get(t,X,Y,ZH);
getans(X,Y,ZH);
if(x==X&&y==Y)getans(X,Y,(zh-ZH)|st[x][y]);
}
int main(){
freopen("in.txt","r",stdin);
int i,j;
n = scan();m = scan();
for(i=two[0]=1;i<=30;i++)two[i] = two[i-1]*2;
for(i=0;i<n;i++)
for(j=0;j<m;j++){
data[i][j] = scan();
if(!data[i][j])st[i][j] = two[cot++];
}
for(int set=0;set<two[cot];set++){
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if(st[i][j]==set)d[i][j][set] = 0;
else d[i][j][set] = MAX;
}
for(int set = 1;set < two[cot];set++){
for(i=0;i<n;i++)
for(j=0;j<m;j++){
if(st[i][j] && (st[i][j] & set)==0)continue;
for(int sub = (set-1)&set;sub;sub = (sub-1)&set){
int tmp = d[i][j][st[i][j]|sub] + d[i][j][st[i][j]|(set-sub)] - data[i][j];
if(tmp < d[i][j][set]){
d[i][j][set] = tmp,from[i][j][set] = pack(i,j,sub|st[i][j]);
// if(!in[i][j][set])dui.push(pack(i,j,set)),in[i][j][set]=1;
}
}
if(d[i][j][set] < MAX)dui.push(pack(i,j,set)),in[i][j][set]=1;
}
spfa();
}
for(i=1;i<n;i++)
for(j=1;j<m;j++)
if(st[i][j]){
printf("%d\n",d[i][j][two[cot]-1]);
getans(i,j,two[cot]-1);
int x,y;
for(x=0;x<n;x++){
for(y=0;y<m;y++){
if(st[x][y])printf("x");
else if(out[x][y])printf("o");
else printf("_");
}
printf("\n");
}
return 0;
}
return 0;
}


  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017