首页 > 代码库 > 【BZOJ2595】【Wc2008】游览计划、斯坦纳树
【BZOJ2595】【Wc2008】游览计划、斯坦纳树
题解:斯坦纳树,实现神马的在代码里面有还看得过去的注释。
代码:
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 15 #define inf 0x3f3f3f3f using namespace std; const int dx[]={0,0,1,-1}; const int dy[]={1,-1,0,0}; struct Point { int x,y; Point(int _x=0,int _y=0):x(_x),y(_y){} }; struct Path { int x,y,s; Path(int _x=0,int _y=0,int _s=0):x(_x),y(_y),s(_s){} }path[N][N][1<<N]; queue<Point>q; int n,m,cnt; int map[N][N],id[N]; int f[N][N][1<<N]; // 别被三维迷惑了,这里的前两维存了坐标 // 第三维才是存的已连接点的压缩状态 bool inq[N][N],used[N][N]; void spfa(int S) { int k,x,y,X,Y; while(!q.empty()) // 一旦某状态被更新了值, // 就可以去再更新一遍别的状态。 { Point U=q.front();q.pop(); inq[x=U.x][y=U.y]=false; for(k=0;k<4;k++) // 向上下左右进行更新 { X=x+dx[k],Y=y+dy[k]; if(x<1||x>n||y<1||y>m)continue; // 不能出界、 if(f[X][Y][S]>f[x][y][S]+map[X][Y]) // 更新值 { f[X][Y][S]=f[x][y][S]+map[X][Y]; path[X][Y][S]=Path(x,y,S); // 记录由什么转移 if(!inq[X][Y])q.push(Point(X,Y)),inq[X][Y]=true; } } } } void dfs(int x,int y,int S) // 乱搞求解 { if(x>inf||!path[x][y][S].s)return ; used[x][y]=1; dfs(path[x][y][S].x,path[x][y][S].y,path[x][y][S].s); if(path[x][y][S].x==x&&path[x][y][S].y==y)dfs(x,y,S^path[x][y][S].s); } int main() { // freopen("test.in","r",stdin); int i,j,k; // 读入 scanf("%d%d",&n,&m); for(i=1;i<=n;i++)for(j=1;j<=m;j++) scanf("%d",&map[i][j]),cnt+=(!map[i][j]); for(i=id[0]=1;i<=cnt;i++)id[i]=id[i-1]<<1; // 初始化一些值 for(i=1;i<=n;i++)for(j=1;j<=m;j++)for(k=0;k<id[cnt];k++) // 初始化 f[i][j][k]=path[i][j][k].x=inf; for(i=1,cnt=0;i<=n;i++)for(j=1;j<=m;j++)if(!map[i][j]) // 景点的f赋0 f[i][j][id[cnt++]]=0; // 注意此处保证了顺序 // 状压求斯坦纳树 int S,s,tmp; for(S=1;S<id[cnt];spfa(S++)) // 枚举点的连通性 for(i=1;i<=n;i++) // 枚举点 for(j=1;j<=m;j++) { for(s=S&(S-1);s;s=S&(s-1))// 枚举集合的子集 Orz Orz 这里不妨调一下看看变量就好了 if((tmp=f[i][j][s]+f[i][j][S^s]-map[i][j])<f[i][j][S]) // 更新f值 { f[i][j][S]=tmp; path[i][j][S]=Path(i,j,s); } if(f[i][j][S]<inf) // 这个状态被更新过,就可以去更新别人了 q.push(Point(i,j)),inq[i][j]=1; } // 求解、 这之后都不是斯坦纳树普遍模板了,乱搞就好 for(i=1;i<=n;i++) { for(j=1;j<=m;j++)if(!map[i][j]) //经过dfs后权值被缩到了一起~ { dfs(i,j,id[cnt]-1); printf("%d\n",f[i][j][id[cnt]-1]); break ; } if(j<=m)break; } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(!map[i][j])putchar('x'); else if(used[i][j])putchar('o'); else putchar('_'); } puts(""); } return 0; }
【BZOJ2595】【Wc2008】游览计划、斯坦纳树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。