当顿时条路所通过的各国一个方都发生志愿者要拖欠方块为风景,否则表示控制该方块至少需要的志愿者数目

【题目叙述】

从今将来了保定的略微 D 有幸参与了Winter Camp2008,他叫立座历史名城的秀丽风景所吸引,强烈要求游览南昌及其周边的兼具景点。

主办者将昆明划分为 N 行M 列(N×M)个方块,如下图(8×8)

 

图片 1

 

风景含于方块内,且一个方至多来一个风景。无景点的正方视为路。

以保证安全暨利,主办方依照路况和治安情状,在非景点的一部分四方内配备不同数量的志愿者;在风景外请导游(导游不是志愿者)。在选拔出境游方案时,保证自由五个风景之间,存在同样条路线,在当时长达路子所经的各级一个四方都来志愿者要欠方块为风景。既能满意选手们游览的内需,又会为志愿者之总数最少。

如,在上边的事例中,在每个没有景色的正方中填入一个数字,表示控制

该方块最少需要的志愿者数目:

 

图片 2

 

图备受之所以深色标出的方区域就是是同等种植中之志愿者安排方案,一共用20称为志愿者。由图可见,五个相邻之景致是直接(有风景内之行程)连通的(如沈园和风水桥)。

今昔,希望您可以援助主办方找到同样栽最好之布局方案。

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

【输入格式】

输入文件被 trip.in 中首先执有星星点点只整数,N 和M,描述方块的数目。

对接下去 N 行,每行有M
独非负整数,如若该整数为0,则该方块为一个色;否则表示控制该方块至少需要之志愿者数目。相邻的整数用(若干独)空格隔开,行首行末也说不定爆发结余的空格。

Description

图片 3.jpg)

图片 4

【输出格式】

出口一行一个平头,即绝少的志愿者总数。

Input

第一实施有零星独整数,N和 M,描述方块的数码。 
联网下 N行, 每行有 M 个非负整数, 假诺该整数为 0,
则该方块为一个景象;
要不然表示控制该方块至少要的志愿者数目。 相邻的平头用 (若干个)
空格隔开,
行首行末也可能有剩余的空格。

【样例输入】

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

Output

是因为 N + 1行组成。第一行一个平头,表示你所吃起的方案
遭配置的志愿者总数目。 
通下去 N行,每行M 个字符,描述方案受到相应方块的情景: 
z  ‘_’(下划线)表示该方块没有配备志愿者; 
z  ‘o’(小写英文字母o)表示该方块安排了志愿者; 
z  ‘x’(小写英文字母x)表示该方块是一个风景; 
注:请小心输出格式要求,假如缺失有平执抑某同尽的字符数目及要求无
一致(任何一样推行遭,多余的空格都不允许出现) ,都可能引致拖欠测试点不得分。

【样例输出】

6

Sample Input

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

【提示】

样例方案:

图片 5

内肉色方块安排了志愿者。

 

不无的 10 组数中N, M ,以及景象数 K 的界定规定如下:

图片 6

输入文件中之拥有整数均无低于 0 且不跳2^16。

 

 

题解:

裸斯坦纳树,直接spfa+子集dp,暴力更新就行.

 

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <queue>
 8 using namespace std;
 9 typedef pair<int,int>par;
10 const int N=12;
11 int n,m,INF,map[N][N],f[N][N][1<<10],S=0,mx[4]={0,0,1,-1},my[4]={1,-1,0,0};
12 bool vis[N][N];
13 queue<par>q;
14 void spfa(int k){
15     for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
16         if(f[i][j][k]!=INF)
17              q.push(par(i,j));
18     int x,y,tx,ty;
19     while(!q.empty()){
20         x=q.front().first;y=q.front().second;q.pop();
21         for(int i=0;i<4;i++){
22             tx=x+mx[i];ty=y+my[i];
23             if(tx<1 || tx>n || ty<1 || ty>m)continue;
24             if(f[x][y][k]+map[tx][ty]<f[tx][ty][k]){
25                 f[tx][ty][k]=f[x][y][k]+map[tx][ty];
26                 if(!vis[tx][ty])q.push(par(tx,ty)),vis[tx][ty]=true;
27             }
28         }
29         vis[x][y]=false;
30     }
31 }
32 void work(){
33     scanf("%d%d",&n,&m);
34     memset(f,127/3,sizeof(f));
35     for(int i=1;i<=n;i++)
36         for(int j=1;j<=m;j++){
37             scanf("%d",&map[i][j]);
38             if(!map[i][j])f[i][j][1<<(S++)]=0;
39         }
40     int states=(1<<S)-1;INF=f[0][0][0];
41     for(int s=1;s<=states;s++){
42         for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
43             for(int k=(k-1)&s;k;k=(k-1)&s){
44                 if(f[i][j][k]+f[i][j][s-k]-map[i][j]<f[i][j][s])
45                     f[i][j][s]=f[i][j][k]+f[i][j][s-k]-map[i][j];
46             }
47          spfa(s);
48     }
49     int ans=INF;
50     for(int i=1;i<=n;i++)
51         for(int j=1;j<=m;j++)
52             if(f[i][j][states]<ans)
53                 ans=f[i][j][states];
54     printf("%d\n",ans);
55 }
56 int main()
57 {
58     freopen("wc2008_trip.in","r",stdin);
59     freopen("wc2008_trip.out","w",stdout);
60     work();
61     return 0;
62 }

 

Sample Output

6
xoox
___o
___o
xoox

HINT

 

 对于100%的数,N,M,K≤10,其中K为景点的数目。输入的备整数均以[0,2^16]的范围外

 

Source

Ljcc930提供SPJ

 

不行肯定是斯坦纳树
$f[i][j][sta]$表示$(i,j)$这一个职位,与其他景点的连通性为$sta$时的顶小花费

换的时段同样栽是枚举子集

其他一样种植是spfa判断,

较套路

 

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int limit = 1050;
const int INF = 1e9;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
#define MP(i,j) make_pair(i,j)
#define se second
#define fi first
#define Pair pair<int,int>
int N, M, tot = 0;
int a[12][12], f[12][12][limit];
int xx[5] = {-1, +1, 0, 0};
int yy[5] = {0, 0, -1, +1};
int vis[12][12];
struct PRE {
    int x, y, S;
}Pre[12][12][limit];
queue<Pair>q;
void SPFA(int cur) {
    while(q.size() != 0) {
        Pair p = q.front();q.pop();
        vis[p.fi][p.se] = 0;
        for(int i = 0; i <4; i++) {
            int wx = p.fi + xx[i], wy = p.se + yy[i];
            if(wx < 1 || wx > N || wy < 1 || wy > M) continue;
            if(f[wx][wy][cur] > f[p.fi][p.se][cur] + a[wx][wy]) {
                f[wx][wy][cur] = f[p.fi][p.se][cur] + a[wx][wy];
                Pre[wx][wy][cur] = (PRE){p.fi, p.se, cur};
                if(!vis[wx][wy])
                    vis[wx][wy] = 1, q.push(MP(wx,wy));
            }
        }
    }
}
void dfs(int x, int y, int now) {
    vis[x][y] = 1;
    PRE tmp = Pre[x][y][now];
    if(tmp.x == 0 && tmp.y == 0) return;
    dfs(tmp.x, tmp.y, tmp.S);
    if(tmp.x == x && tmp.y == y) dfs(tmp.x, tmp.y, now - tmp.S);
}
int main() {
    N = read(); M = read();
    memset(f, 0x3f, sizeof(f));
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++) {
            a[i][j] = read();
            if(a[i][j] == 0)
                f[i][j][1 << tot] = 0, tot++;
        }
    int limit = (1 << tot) - 1;
    for(int sta = 0; sta <= limit; sta++) {
        for(int i = 1; i<= N; i++)
            for(int j = 1; j <= M;j++) {
                for(int s = sta & (sta - 1); s; s = (s - 1) & sta) {
                    if(f[i][j][s] + f[i][j][sta - s] - a[i][j] < f[i][j][sta])
                        f[i][j][sta] = f[i][j][s] + f[i][j][sta - s] - a[i][j],
                        Pre[i][j][sta] = (PRE){i,j,s};
                }
                if(f[i][j][sta] < INF) q.push(MP(i,j)), vis[i][j] = 1;
            }
        SPFA(sta);
    }
    int ansx, ansy, flag = 0;
    for(int i = 1; i <= N && !flag; i++)
        for(int j = 1; j <= M; j++)
            if(!a[i][j]) 
                {ansx = i, ansy = j; flag = 1; break;}
    printf("%d\n",f[ansx][ansy][limit]); 
    memset(vis, 0, sizeof(vis));
    dfs(ansx, ansy, limit);
    for(int i = 1; i <= N; i++, puts("")) {
        for(int j = 1; j <= M; j++) {
            if(a[i][j] == 0) putchar('x');
            else if(vis[i][j]) putchar('o');
            else putchar('_');            
        } 
    } 
    return 0;
}

 

相关文章