首页 > 代码库 > 【BZOJ】【2595】【WC2008】游览计划

【BZOJ】【2595】【WC2008】游览计划

2024-10-21 14:16:39   202人阅读

Orz zky神犇http://blog.csdn.net/iamzky/article/details/42029921

spfa的灵活应用！（好像是求了一个叫做斯坦纳树的东西……）

o(︶︿︶)o 唉我就是太水了，离散化写跪了，x*1e5+y*1e4+k，但是这题里我x和y的范围是[1,10]所以在y==10的时候会出错！！

技术分享
  1 //BZOJ 2595  2 #include<queue>  3 #include<cmath>  4 #include<cstdio>  5 #include<cstring>  6 #include<cstdlib>  7 #include<iostream>  8 #include<algorithm>  9 #define rep(i,n) for(int i=0;i<n;++i) 10 #define F(i,j,n) for(int i=j;i<=n;++i) 11 #define D(i,j,n) for(int i=j;i>=n;--i) 12 using namespace std; 13 const int N=13,INF=~0u>>2; 14 const int fx[]={1,0,-1,0}, 15           fy[]={0,1,0,-1}; 16 typedef long long LL; 17 //#define debug 18 int n,m,a[N][N],d[N][N],cnt=0; 19 int f[N][N][1100],pre[N][N][1100]; 20 bool vis[N][N]; 21  22 struct node{ int x,y; }; 23 queue<node>Q; 24 inline int pack(int x,int y,int s){ 25     return x*1000000+y*10000+s; 26 } 27  28 void spfa(int Set){ 29     while(!Q.empty()){ 30         int x=Q.front().x,y=Q.front().y; Q.pop(); 31         vis[x][y]=0; 32         rep(i,4){ 33             int tx=x+fx[i],ty=y+fy[i]; 34             if (tx<1 || ty<1 || tx>n || ty>m) continue; 35              36             if (f[tx][ty][Set]>f[x][y][Set]+a[tx][ty]){ 37                 f[tx][ty][Set]=f[x][y][Set]+a[tx][ty]; 38                 pre[tx][ty][Set]=pack(x,y,Set); 39                 if (!vis[tx][ty]) Q.push((node){tx,ty}),vis[tx][ty]=1; 40             } 41         } 42     } 43 } 44  45 void dfs(int i,int j,int Set){ 46     if (pre[i][j][Set]==INF || pre[i][j][Set]%5000==0)return; 47     vis[i][j]=1; 48     int x=pre[i][j][Set]/1000000, 49     y=(pre[i][j][Set]-x*1000000)/10000, 50     z=(pre[i][j][Set]-x*1000000-y*10000); 51     #ifdef debug 52     printf("%d,%d,%d----->%d,%d,%d\n",x,y,z,i,j,Set); 53     #endif 54     dfs(x,y,z); 55     if (x==i && y==j) dfs(i,j,Set-z); 56 } 57  58 void solve(){ 59     for(int Set=1;Set<(1<<cnt);Set++){ 60         F(x,1,n) F(y,1,m){ 61             for(int s=Set&(Set-1);s;s=(s-1)&Set){ 62                 if(f[x][y][Set]>f[x][y][s]+f[x][y][Set-s]-a[x][y]){ 63                     f[x][y][Set]=f[x][y][s]+f[x][y][Set-s]-a[x][y]; 64                     pre[x][y][Set]=pack(x,y,s); 65                 } 66             } 67             if (f[x][y][Set]!=INF){Q.push((node){x,y}); vis[x][y]=1;} 68         } 69         spfa(Set); 70     } 71     int x,y; 72     F(i,1,n) F(j,1,m) if (!a[i][j]) {x=i; y=j;break;} 73     printf("%d\n",f[x][y][(1<<cnt)-1]); 74      75     #ifdef debug 76     F(i,1,n) F(j,1,m) 77         F(k,0,(1<<cnt)-1)  78             if (pre[i][j][k]!=INF)  79             printf("pre[%d][%d][%d]=%d\n",i,j,k,pre[i][j][k]); 80     #endif  81     dfs(x,y,(1<<cnt)-1); 82     F(i,1,n) F(j,1,m){ 83         if (!a[i][j]) putchar(‘x‘); 84         else if(vis[i][j]) putchar(‘o‘); 85         else putchar(‘_‘); 86         if (j==m) puts(""); 87     } 88 } 89  90 int main(){ 91     #ifndef ONLINE_JUDGE 92     freopen("file.in","r",stdin); 93 //    freopen("file.out","w",stdout); 94     #endif 95     scanf("%d%d",&n,&m); 96     F(i,0,10) F(j,0,10) 97         F(k,0,(1<<10)) f[i][j][k]=pre[i][j][k]=INF; 98     F(i,1,n) 99         F(j,1,m){100             scanf("%d",&a[i][j]);101             if (!a[i][j])102                 f[i][j][1<<(cnt++)]=0;103         }104     solve();105     return 0;106 }
View Code

 

【BZOJ】【2595】【WC2008】游览计划


联系
我们