【BZOJ-2595】游览计划斯坦纳树-白红宇

【BZOJ-2595】游览计划斯坦纳树

阅读量：5106 次

发布时间：2019-06-13

本文共 2367 字，大约阅读时间需要 7 分钟。

2595: [Wc2008]游览计划

Time Limit: 10 Sec Memory Limit: 256 MBSec Special Judge

Submit: 1518 Solved: 714

[][][]

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

xoox

___o

xoox

HINT

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

Source

Solution

现在就是留下板子走人= =

状压dp+spfa松弛一下就可以了。

自己写个破烂模板还要调一会= =，写完后发现网上绝大部分的人都是三个数压起来，只有我弱智的记下来。

Code

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define INF 0xf0f0f0f#define Pa pair
            
             #define PPa pair
             
              #define fi first#define se second#define MP make_pairPa nidx[150];PPa nidp[250000];int N,S,M,mp[11][11],bin[11][11];int idx[11][11],idp[11][11][1<<10],dp[11][11][1<<10],fr[11][11][1<<10];inline void Update(int nx,int ny,int nz,int ox,int oy,int oz,int z){ if (dp[nx][ny][nz]>z) dp[nx][ny][nz]=z,fr[nx][ny][nz]=idp[ox][oy][oz];}int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},visit[150];queue
              
               q;inline void Spfa(int sta){ while (!q.empty()) { int now=q.front(); visit[now]=0; q.pop(); int x=nidx[now].fi,y=nidx[now].se; for (int d=0; d<4; d++) { int tx=x+dx[d],ty=y+dy[d]; if (!tx || !ty || tx>N || ty>M) continue; if (dp[tx][ty][sta]>dp[x][y][sta]+mp[tx][ty]) { Update(tx,ty,sta,x,y,sta,dp[x][y][sta]+mp[tx][ty]); if (!visit[idx[tx][ty]]) q.push(idx[tx][ty]),visit[idx[tx][ty]]=1; } } }}bool mark[11][11];inline void Dfs(int x,int y,int sta){ if (!fr[x][y][sta]) return; mark[x][y]=1; int now=fr[x][y][sta]; int tx=nidp[now].fi.fi,ty=nidp[now].fi.se,ts=nidp[now].se; Dfs(tx,ty,ts); if (tx==x && ty==y) Dfs(tx,ty,sta-ts); }int main(){ memset(dp,0xf,sizeof(dp)); scanf("%d%d",&N,&M); for (int i=1; i<=N; i++) for (int j=1; j<=M; j++) { scanf("%d",&mp[i][j]); if (!mp[i][j]) bin[i][j]=1<<(S++),dp[i][j][bin[i][j]]=0; } for (int i=1,Idx=0,Idp=0; i<=N; i++) for (int j=1; j<=M; j++) { idx[i][j]=++Idx; nidx[Idx]=MP(i,j); for (int k=0; k<(1<