首页 > 代码库 > BZOJ 2595: [Wc2008]游览计划 [DP 状压 斯坦纳树 spfa]【学习笔记】

BZOJ 2595: [Wc2008]游览计划 [DP 状压 斯坦纳树 spfa]【学习笔记】

2024-09-07 08:32:02   216人阅读

传送门

题意：略

 

论文 《SPFA算法的优化及应用》

http://www.cnblogs.com/lazycal/p/bzoj-2595.html

本题的核心就是求斯坦纳树：

Steiner Tree:

Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals, 

the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals (but may include additional vertices). 

也就是对于给定的点集求一颗包含他的最小生成树(可以包含额外的点)

$ST$是$NPC$问题，规模小的情况可以使用状压$DP$解决

 

$f[i][s]$表示根在$i$，连通的点集为$s$的(仅包括给定点集中的点)的最小花费

有两种转移：

对于点权的情况（边权类似）：

$f[i][s]=min{f[i][s‘]+f[i][s-s‘]-val[i]}$，划分成两个子集，具有阶段性普通$DP$就可以

$f[i][s]=min{f[i‘][s]+val[i]}$，从一颗树扩展而来，阶段性不明显，但满足三角不等式，使用$spfa$求解

那么过程就很清楚了

  • 从小到大枚举集合和点
  • 第一种转移枚举子集
  • 第二种转移对当前集合使用spfa

 

然后就到黄学长哪里仿写了份模板

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <queue>using namespace std;#define pii pair<int,int>#define MP make_pair#define fir first#define sec secondtypedef long long ll;const int N=12,S=(1<<10)+5,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;}int n,m,k,a[N][N];int f[N][N][S];struct Path{    int i,j,s;    Path(){}    Path(int a,int b,int c):i(a),j(b),s(c){}}pre[N][N][S];queue<pii> q;bool inq[N][N];int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};void spfa(int s){    while(!q.empty()){        int x=q.front().fir,y=q.front().sec;        inq[x][y]=0;q.pop();        for(int k=0;k<4;k++){            int i=x+dx[k],j=y+dy[k];            if(i<1||i>n||j<1||j>m) continue;            if(f[i][j][s]>f[x][y][s]+a[i][j]){                f[i][j][s]=f[x][y][s]+a[i][j];                pre[i][j][s]=Path(x,y,s);                if(!inq[i][j])                    q.push(MP(i,j)),inq[i][j]=1;            }        }    }}bool vis[N][N];void dfs(int x,int y,int s){    vis[x][y]=1;    Path t=pre[x][y][s];    if(t.i==0&&t.j==0) return;    dfs(t.i , t.j , t.s);    if(t.i==x && t.j==y) dfs(t.i , t.j , s-t.s);}int main(){    freopen("in","r",stdin);    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]) f[i][j][1<<k]=0,k++;        }    int All=1<<k;    for(int sa=0;sa<All;sa++){        for(int i=1;i<=n;i++)            for(int j=1;j<=m;j++){                for(int s=sa&(sa-1);s;s=sa&(s-1)){                    int _=f[i][j][s]+f[i][j][sa-s]-a[i][j];                    if(_<f[i][j][sa]){                        f[i][j][sa]=_;                        pre[i][j][sa]=Path(i,j,s);                    }                }                if(f[i][j][sa]<INF) q.push(MP(i,j)),inq[i][j]=1;            }        spfa(sa);    }    int x=0,y=0,flag=0;    for(int i=1;i<=n&&!flag;i++)         for(int j=1;j<=m;j++) if(!a[i][j]) {x=i;y=j;flag=1;break;}    dfs(x,y,All-1);    printf("%d\n",f[x][y][All-1]);    for(int i=1;i<=n;i++){        for(int j=1;j<=m;j++){            if(a[i][j]==0) putchar(‘x‘);            else if(vis[i][j]) putchar(‘o‘);            else putchar(‘_‘);        }        puts("");    }}

 

BZOJ 2595: [Wc2008]游览计划 [DP 状压 斯坦纳树 spfa]【学习笔记】


联系
我们