首页 > 代码库 > [BZOJ2595][Wc2008]游览计划
[BZOJ2595][Wc2008]游览计划
[BZOJ2595][Wc2008]游览计划
试题描述
输入
第一行有两个整数,N和 M,描述方块的数目。
接下来 N行, 每行有 M 个非负整数, 如果该整数为 0, 则该方块为一个景点;
否则表示控制该方块至少需要的志愿者数目。 相邻的整数用 (若干个) 空格隔开,
行首行末也可能有多余的空格。
输出
由 N + 1行组成。第一行为一个整数,表示你所给出的方案
中安排的志愿者总数目。
接下来 N行,每行M 个字符,描述方案中相应方块的情况:
z ‘_’(下划线)表示该方块没有安排志愿者;
z ‘o’(小写英文字母o)表示该方块安排了志愿者;
z ‘x’(小写英文字母x)表示该方块是一个景点;
注:请注意输出格式要求,如果缺少某一行或者某一行的字符数目和要求不
一致(任何一行中,多余的空格都不允许出现) ,都可能导致该测试点不得分。
输入示例
4 4 0 1 1 0 2 5 5 1 1 5 5 1 0 1 1 0
输出示例
6
数据规模及约定
对于100%的数据,N,M,K≤10,其中K为景点的数目。输入的所有整数均在[0,2^16]的范围内
题解
听说叫斯坦纳树,其实是一个状压 dp。这个 dp 挺奇怪的,大概是设 f[i][j][S] 表示包含了 (i, j) 的连通块中至少包含集合 S 中所有景点的最小代价。具体请看这里。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <algorithm> #include <queue> using namespace std; int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); } return x * f; } #define maxn 11 #define maxs 1030 #define oo 2147483647 int n, m, K, A[maxn][maxn], f[maxn][maxn][maxs]; struct Sta { int x, y, S; Sta(): x(0), y(0), S(0) {} Sta(int _1, int _2, int _3): x(_1), y(_2), S(_3) {} } fa[maxn][maxn][maxs]; bool up(Sta to, Sta from, int val) { if(f[to.x][to.y][to.S] > val) { f[to.x][to.y][to.S] = val, fa[to.x][to.y][to.S] = from; return 1; } return 0; } queue <Sta> Q; bool inq[maxn][maxn]; void init() { memset(inq, 0, sizeof(inq)); while(!Q.empty()) Q.pop(); return ; } int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; bool inside(Sta x) { return 1 <= x.x && x.x <= n && 1 <= x.y && x.y <= m; } void expend() { while(!Q.empty()) { Sta u = Q.front(); Q.pop(); inq[u.x][u.y] = 0; for(int i = 0; i < 4; i++) { Sta v(u.x + dx[i], u.y + dy[i], u.S); if(inside(v) && up(v, u, f[u.x][u.y][u.S] + A[v.x][v.y]) && !inq[v.x][v.y]) inq[v.x][v.y] = 1, Q.push(v); } } return ; } bool put[maxn][maxn]; void Path(Sta u) { if(!u.S) return ; put[u.x][u.y] = 1; Sta v = fa[u.x][u.y][u.S]; Path(v); if(v.S != u.S && v.S) Path(Sta(v.x, v.y, u.S - v.S)); return ; } int main() { n = read(); m = read(); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) for(int S = 0; S < maxs; S++) f[i][j][S] = oo; int p = 0; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { A[i][j] = read(); if(!A[i][j]) f[i][j][1<<p++] = 0; } int all = (1 << p) - 1; for(int S = 1; S <= all; S++) { init(); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { for(int Sub = S & S - 1; Sub; Sub = S & Sub - 1) if(f[i][j][Sub] < oo && f[i][j][S-Sub] < oo) up(Sta(i, j, S), Sta(i, j, Sub), f[i][j][Sub] + f[i][j][S-Sub] - A[i][j]); if(f[i][j][S] < oo) Q.push(Sta(i, j, S)), inq[i][j] = 1; } expend(); } for(int i = 1; i <= n; i++) { bool has = 0; for(int j = 1; j <= m; j++) if(!A[i][j]) { printf("%d\n", f[i][j][all]); Path(Sta(i, j, all)); for(int a = 1; a <= n; a++) { for(int b = 1; b <= m; b++) if(!A[a][b]) putchar(‘x‘); else if(put[a][b]) putchar(‘o‘); else putchar(‘_‘); putchar(‘\n‘); } has = 1; break; } if(has) break; } return 0; }
[BZOJ2595][Wc2008]游览计划
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。