「BZOJ2595」[Wc2008] 游览计划
Description
.jpg)
Input
第一行有两个整数，N和 M，描述方块的数目。
接下来 N行， 每行有 M 个非负整数， 如果该整数为 0， 则该方块为一个景点；
否则表示控制该方块至少需要的志愿者数目。 相邻的整数用 （若干个） 空格隔开，
行首行末也可能有多余的空格。
Output
由 N + 1行组成。第一行为一个整数，表示你所给出的方案
中安排的志愿者总数目。
接下来 N行，每行M 个字符，描述方案中相应方块的情况：
z ‘_’（下划线）表示该方块没有安排志愿者；
z ‘o’（小写英文字母o）表示该方块安排了志愿者；
z ‘x’（小写英文字母x）表示该方块是一个景点；
注：请注意输出格式要求，如果缺少某一行或者某一行的字符数目和要求不
一致（任何一行中，多余的空格都不允许出现） ，都可能导致该测试点不得分。
中安排的志愿者总数目。
接下来 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
0 1 1 0
2 5 5 1
1 5 5 1
0 1 1 0
Sample Output
6
xoox
___o
___o
xoox
xoox
___o
___o
xoox
HINT
对于100%的数据，N,M,K≤10，其中K为景点的数目。输入的所有整数均在[0,2^16]的范围内
题解
斯坦纳树
大家一起orz zky吧
http://blog.csdn.net/iamzky/article/details/42029921
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
#include<cstdio> #include<cmath> #include<cstring> #include<iostream> #include<queue> #define pa pair<int,int> #define ll long long #define inf 100000000 using namespace std; int read() { int x=0;char ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int a[15][15]; int bin[20]; int n,m,K; int f[12][12][1024]; struct data{ int fit,sed,thd; }pre[15][15][1024]; int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0}; queue<pa>q; bool inq[15][15],vis[15][15]; void spfa(int sta) { while(!q.empty()) { int x=q.front().first,y=q.front().second; inq[x][y]=0;q.pop(); for(int k=0;k<4;k++) { int nowx=x+xx[k],nowy=y+yy[k]; if(x<1||y<1||x>n||y>m)continue; if(f[nowx][nowy][sta]>f[x][y][sta]+a[nowx][nowy]) { f[nowx][nowy][sta]=f[x][y][sta]+a[nowx][nowy]; pre[nowx][nowy][sta]=(data){x,y,sta}; if(!inq[nowx][nowy]) { q.push(make_pair(nowx,nowy)); inq[nowx][nowy]=1; } } } } } void dfs(int x,int y,int sta) { if(x>inf||pre[x][y][sta].thd==0)return; vis[x][y]=1; data t=pre[x][y][sta]; dfs(t.fit,t.sed,t.thd); if(t.fit==x&&t.sed==y)dfs(x,y,sta-t.thd); } int main() { bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; n=read();m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { a[i][j]=read(); if(!a[i][j])K++; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k<bin[K];k++) f[i][j][k]=pre[i][j][k].fit=inf; K=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(!a[i][j]) f[i][j][bin[K]]=0,K++; for(int sta=1;sta<bin[K];sta++) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { for(int s=sta&(sta-1);s;s=sta&(s-1)) { int t=f[i][j][s]+f[i][j][sta-s]-a[i][j]; if(t<f[i][j][sta]) { f[i][j][sta]=t; pre[i][j][sta]=(data){i,j,s}; } } if(f[i][j][sta]<inf) q.push(make_pair(i,j)),inq[i][j]=1; }spfa(sta); } int x,y; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(!a[i][j]) { x=i;y=j;break; } dfs(x,y,bin[K]-1); printf("%d\n",f[x][y][bin[K]-1]); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(!a[i][j])printf("x"); else if(vis[i][j])printf("o"); else printf("_"); } puts(""); } return 0; } |
计数器 9302694
OI 课件=>
OI 课件=>
另外第52行的那个x>inf应该是x>=inf
黄学长的第36行的那个程序应该把x改成nowx，y改成nowy吧，我纯口胡。。。
扑通扑通跪下来，千古神犇黄哲威
发现看着学长的博客，受益匪浅，orz zky