首页 > 代码库 > [Wc2008]游览计划

[Wc2008]游览计划

2024-10-12 10:29:02   210人阅读

2595: [Wc2008]游览计划

Time Limit: 10 Sec  Memory Limit: 256 MBSec  Special Judge
[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]的范围内

 

Source

Ljcc930提供SPJ

斯坦纳树

#include<cstring>#include<cstdio>#include<queue>#include<algorithm>#define N 1<<10using namespace std;int n,m,sum;int f[11][11][N+1],g[N+1],a[12][12];bool v[10000],vis[11][11];int dx[4]={-1,0,1,0};int dy[4]={0,1,0,-1};struct node{    int xx,yy,st;}pre[11][11][N];queue<int>q;void dfs(int i,int j,int s){         if(!pre[i][j][s].st) return;    vis[i][j]=true;    dfs(pre[i][j][s].xx,pre[i][j][s].yy,pre[i][j][s].st);    if(pre[i][j][s].xx==i && pre[i][j][s].yy==j)  dfs(i,j,s^pre[i][j][s].st);}int main(){    memset(f,0x3f3f3f3f,sizeof(f));     scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)      for(int j=1;j<=m;j++)        {            scanf("%d",&a[i][j]);            if(!a[i][j]) f[i][j][1<<sum++]=0;        }    int h,l,now,oo=f[0][0][0],x,y;    for(int S=1;S<(1<<sum);S++)    {        for(int i=1;i<=n;i++)        {            for(int j=1;j<=m;j++)            {                for(int T=S-1;T;T=(T-1)&S)                {                    if(f[i][j][T]+f[i][j][T^S]-a[i][j]<f[i][j][S])                    {                        f[i][j][S]=f[i][j][T]+f[i][j][T^S]-a[i][j];                        pre[i][j][S]=node{i,j,T};                    }                }                if(f[i][j][S]<oo) q.push(i*100+j),v[i*100+j]=true;            }        }        while(!q.empty())        {            now=q.front(); q.pop(); v[now]=false;            h=now/100; l=now%100;            for(int j=0;j<4;j++)            {                x=h+dx[j]; y=l+dy[j];                if(x<1||x>n||y<1||y>m) continue;                if(f[x][y][S]>f[h][l][S]+a[x][y])                {                    f[x][y][S]=f[h][l][S]+a[x][y];                    pre[x][y][S]=node{h,l,S};                    if(!v[x*100+y])                    {                        q.push(x*100+y);                        v[x*100+y]=true;                    }                }            }        }    }    for(int i=1;i<=n;i++)      for(int j=1;j<=m;j++)        if(!a[i][j])        {            printf("%d\n",f[i][j][(1<<sum)-1]);            dfs(i,j,(1<<sum)-1);            for(int h=1;h<=n;h++)            {                for(int l=1;l<=m;l++)                 if(!a[h][l]) putchar(‘x‘);                 else if(vis[h][l]) putchar(‘o‘);                 else putchar(‘_‘);                puts("");            }            return 0;        }}

 

[Wc2008]游览计划


联系
我们