P4294 [WC2008]游览计划

题意

斯坦纳树裸题。

显然答案是棵树。

设\(f[i][s]\)表示以\(i\)为根，集合为\(s\)的最小代价。

先在同根之间转移：
\(f[i][s]=min(f[i][t]+f[i][s\ xor\ t]-val[i])\)
减\(val[i]\)是因为算了两遍。
之后扩展新点：
\(f[i][s]=min(f[j][s]+val[i]),(i,j)\)联通，这个可以用\(spfa\)。

code:

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mkp make_pair
#define fir first
#define sec second
const int maxn=12;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
int n,m,K,tot,root,ans=0x3f3f3f3f;
int id[maxn][maxn],a[maxn][maxn],f[maxn*maxn][1<<maxn];
pii pos[maxn*maxn],g[maxn*maxn][1<<maxn];
bool vis[maxn*maxn];
bool check[maxn][maxn];
vector<int>keypoints;
queue<int>q;
inline void spfa(int s)
{
    while(!q.empty())
    {
        int x=q.front();q.pop();vis[x]=0;
        for(int i=0;i<4;i++)
        {
            int mx=pos[x].fir+dx[i],my=pos[x].sec+dy[i];
            if(mx<1||mx>n||my<1||my>m)continue;
            int y=id[mx][my];
            if(f[y][s]>f[x][s]+a[pos[y].fir][pos[y].sec])
            {
                f[y][s]=f[x][s]+a[pos[y].fir][pos[y].sec];
                if(!vis[y])vis[y]=1,q.push(y);
                g[y][s]=mkp(x,s);
            }
        }
    }
}
void dfs(int now,int s)
{
    if(!g[now][s].sec)return;
    check[pos[now].fir][pos[now].sec]=1;
    if(g[now][s].fir==now)dfs(now,s^g[now][s].sec);
    dfs(g[now][s].fir,g[now][s].sec);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]),id[i][j]=++tot,pos[tot]=mkp(i,j);
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(!a[i][j])f[id[i][j]][1<<K]=0,K++,keypoints.push_back(id[i][j]);
    for(int s=1;s<(1<<K);s++)
    {
        for(int i=1;i<=n*m;i++)
        {
            for(int t=s&(s-1);t;t=(t-1)&s)
                if(f[i][s]>f[i][s^t]+f[i][t]-a[pos[i].fir][pos[i].sec])
                {
                    f[i][s]=f[i][s^t]+f[i][t]-a[pos[i].fir][pos[i].sec];
                    g[i][s]=mkp(i,t);
                }
            if(f[i][s]<0x3f3f3f3f)q.push(i),vis[i]=1;
        }
        spfa(s);
    }
    for(unsigned int i=0;i<keypoints.size();i++)
        if(ans>f[keypoints[i]][(1<<K)-1])ans=f[keypoints[i]][(1<<K)-1],root=keypoints[i];
    printf("%d\n",ans);
    dfs(root,(1<<K)-1);
    for(int i=1;i<=n;i++,puts(""))
        for(int j=1;j<=m;j++)
            if(!a[i][j])putchar('x');
            else putchar(check[i][j]?'o':'_');
    return 0;
}