bzoj2595 [Wc2008]游览计划——斯坦纳树

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2595

今天刚学了斯坦纳树，还不太会，写一道题练习一下；

参考了博客：http://www.cnblogs.com/lazycal/archive/2013/08/31/bzoj-2595.html

代码也是模仿着写的，感觉有了更深的理解；

总之，大概就是两种转移方式，合并转移枚举子集即可，最短路转移用 spfa；

还要记录一个 pre 用来找到连通块内的点；

用哈希一样的方法把几个数 pack 起来的写法真神奇啊；

说实话还是有点云里雾里，不过成功写出了第一道斯坦纳树的题，感觉很好！

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

int const maxn=,inf=0x3f3f3f3f;

int n,m,K,mx,f[maxn][maxn][<<maxn],a[maxn][maxn],pre[maxn][maxn][<<maxn];

int dx[]={,,-,},dy[]={,,,-};

bool vis[maxn][maxn],inq[maxn*maxn];

queue<int>q;

int pack(int i,int j){return i*+j;}

int pack2(int i,int j,int s){return i*+j*+s;}

void unpack(int x,int &i,int &j){i=x/; j=x%;}

void unpack2(int x,int &i,int &j,int &s){i=x/; j=(x/)%; s=x%;}

bool update(int x,int y,int s,int i,int j,int sta,int w)

{

    if(f[x][y][s]>w){f[x][y][s]=w; pre[x][y][s]=pack2(i,j,sta); return ;}

    return ;

}

void spfa(int sta)

{

    while(q.size())

    {

        int i,j;

        unpack(q.front(),i,j); inq[q.front()]=; q.pop();

        for(int k=;k<;k++)

        {

            int x=i+dx[k],y=j+dy[k],tmp;

            if(x==-||y==-||x==n||y==m)continue;//!!!

            if(update(x,y,sta,i,j,sta,f[i][j][sta]+a[x][y])&&!inq[tmp=pack(x,y)])//不改变连通性

                q.push(tmp),inq[tmp]=;

        }

    }

}

void dfs(int x,int y,int sta)

{

    if(!pre[x][y][sta])return;

    vis[x][y]=;

    int i,j,s;

    unpack2(pre[x][y][sta],i,j,s);

    dfs(i,j,s);

    if(i==x&&j==y)dfs(i,j,sta-s);//合并转移

}

void print()

{

    for(int i=;i<n;i++)

    {

        for(int j=;j<m;j++)

        {

            if(!a[i][j])printf("x");

            else if(vis[i][j])printf("o");

            else printf("_");

        }

        printf("\n");

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    memset(f,0x3f,sizeof f);

    for(int i=;i<n;i++)

        for(int j=;j<m;j++)

        {

            scanf("%d",&a[i][j]);

            if(!a[i][j])f[i][j][<<(K++)]=;

        }

    mx=(<<K);

    for(int sta=;sta<mx;sta++)

    {

        for(int i=;i<n;i++)

            for(int j=,tmp;j<m;j++)//以(i,j)为媒介

            {

                for(int s=(sta&(sta-));s;s=(s-)&sta)

                    update(i,j,sta,i,j,s,f[i][j][s]+f[i][j][sta-s]-a[i][j]);//点权重复

                if(f[i][j][sta]!=inf)q.push(tmp=pack(i,j)),inq[tmp]=;//inq!

            }

        spfa(sta);//更新不同位置的sta

    }

    for(int i=;i<n;i++)

        for(int j=;j<m;j++)

            if(!a[i][j])

            {

                printf("%d\n",f[i][j][mx-]);

                dfs(i,j,mx-);

                print();

                return ;

            }

}