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

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2595][Wc2008]游览计划  

2015-06-20 19:40:04|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2595: [Wc2008]游览计划

Time Limit: 10 Sec  Memory Limit: 256 MBSec  Special Judge
Submit: 813  Solved: 323
[Submit][Status][Discuss]

Description

Input

第一行有两个整数,N和 M,描述方块的数目。 
接下来 N行, 每行有 M 个非负整数, 如果该整数为 0, 则该方块为一个景点;
否则表示控制该方块至少需要的志愿者数目。 相邻的整数用 (若干个) 空格隔开,
行首行末也可能有多余的空格。

Output

由 N + 1行组成。第一行为一个整数,表示你所给出的方案
中安排的志愿者总数目。 
接下来 N行,每行M 个字符,描述方案中相应方块的情况: 
z  ‘_’(下划线)表示该方块没有安排志愿者; 
z  ‘o’(小写英文字母o)表示该方块安排了志愿者; 
z  ‘x’(小写英文字母x)表示该方块是一个景点; 
注:请注意输出格式要求,如果缺少某一行或者某一行的字符数目和要求不
一致(任何一行中,多余的空格都不允许出现) ,都可能导致该测试点不得分。

Sample Input

4 4 0 1 1 0 2 5 5 1 1 5 5 1 0 1 1 0

Sample Output

6 xoox ___o ___o xoox

HINT

 对于100%的数据,N,M,K≤10,其中K为景点的数目。输入的所有整数均在[0,2^16]的范围内

Solution

f[i][j][s]->点(i,j),当前联通的点集为s
f[i][j][s]=f[i][j][s']+f[i][j][s-s']-a[i][j](将两个树的头粘在一起)
f[i][j][s]=min(f[i][j][s],f[x][y][s]+a[i][j])(长叶子)->spfa

Code

/**************************************************************
    Problem: 2595
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:176 ms
    Memory:3188 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
int f[1024][12][12],n,m,k,a[12][12],tot,i,j,s,oo,l,r,q[10000][2],in[12][12],vis[12][12];char ans[12][12];
int dx[]={-1,0,0,1},dy[]={0,-1,1,0};
struct D{int s,x,y;}pre[1024][12][12],tmp;
void spfa(int s){int x,y,k,nx,ny;
    for(;l<=r;in[x][y]=0,l++)
    for(x=q[l][0],y=q[l][1],k=0;k<4;k++)
    if(nx=x+dx[k],ny=y+dy[k],nx>0&&nx<=n&&ny>0&&ny<=m&&f[s][nx][ny]>f[s][x][y]+a[nx][ny]){
        f[s][nx][ny]=f[s][x][y]+a[nx][ny],pre[s][nx][ny]=(D){s,x,y};
        if(!in[nx][ny])r++,q[r][0]=nx,q[r][1]=ny,in[nx][ny]=1;
    }
}
#define rep for(i=1;i<=n;i++)for(j=1;j<=m;j++)
void dfs(int s,int x,int y){
    if(!s||!x||!y)return;
    vis[x][y]=1;D&tmp=pre[s][x][y];
    dfs(tmp.s,tmp.x,tmp.y);
    if(tmp.x==x&&tmp.y==y)dfs(s^tmp.s,tmp.x,tmp.y);
}
int main(){
    scanf("%d%d",&n,&m);memset(f,63,sizeof(f)),oo=f[0][0][0];
    rep scanf("%d",&a[i][j]),!a[i][j]?f[1<<(tot++)][i][j]=0:1;
    for(s=1;s<1<<tot;spfa(s++))
    for(l=1,r=0,i=1;i<=n;i++)
    for(j=1;j<=m;f[s][i][j]<oo?r++,q[r][0]=i,q[r][1]=j,in[i][j]=1:1,j++)
    for(k=s;k=s&(k-1);)
    if(f[s][i][j]>f[k][i][j]+f[s^k][i][j]-a[i][j])
    f[s][i][j]=f[k][i][j]+f[s^k][i][j]-a[i][j],pre[s][i][j]=(D){k,i,j};
    rep if(!a[i][j]){tot=(1<<tot)-1;
        printf("%d\n",f[tot][i][j]);dfs(tot,i,j);
        rep if(a[i][j]==0)ans[i][j]='x';
        else if(vis[i][j])ans[i][j]='o';
        else ans[i][j]='_';
        for(i=1;i<=n;i++)puts(ans[i]+1);
        return 0;
    }
}

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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