【题目分析】
斯坦纳树=子集DP+SPFA？
用来学习斯坦纳树的模板。
大概就是用二进制来表示树包含的点，然后用跟几点表示树的形态。
更新分为两种，一种是合并两个子集，一种是换根，换根用SPFA迭代即可。
【代码】
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath> #include <set>
#include <map>
#include <string>
#include <algorithm>
#include <vector>
#include <iostream>
#include <queue> using namespace std; #define maxn 11
#define F(i,j,k) for (int i=j;i<=k;++i)
#define inf (0x3f3f3f3f) int Getint()
{
int x=0,f=1; char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
} int n,m,a[maxn][maxn],cnt=0,dp[maxn][maxn][1<<maxn],pre[maxn][maxn][1<<maxn][4];
queue <int> qi,qj;
int inq[maxn][maxn],b[maxn][maxn];
int mov[4][2]={0,1,1,0,-1,0,0,-1}; void dfs(int x,int y,int k)
{
// cout<<"dfs "<<x<<" "<<y<<" "<<k<<endl;
// getchar();
if (!k||!x||!y) return;
b[x][y]=1;
dfs(pre[x][y][k][0],pre[x][y][k][1],pre[x][y][k][2]);
if (pre[x][y][k][2]!=k) dfs(pre[x][y][k][0],pre[x][y][k][1],k^pre[x][y][k][2]);
// if (pre[x][y][k][0]==x&&pre[x][y][k][1]==y) dfs(pre[x][y][k][0],pre[x][y][k][1],k^pre[x][y][k][2]);
} void out()
{
F(i,1,n)
{
F(j,1,m)
if (b[i][j])
{
if (a[i][j]) printf("o");
else printf("x");
}
else
{
printf("_");
}
printf("\n");
}
} int main()
{
memset(dp,0x3f,sizeof dp);
n=Getint();m=Getint();
F(i,1,n) F(j,1,m)
{
a[i][j]=Getint();
if(!a[i][j])
{
cnt++;
dp[i][j][1<<(cnt-1)]=0;
}
}
for (int k=1;k<(1<<cnt);++k)
{
F(i,1,n) F(j,1,m)
{
for (int x=(k-1)&k;x;x=(x-1)&k)
{
int tmp=dp[i][j][x]+dp[i][j][k^x]-a[i][j];
if (tmp<dp[i][j][k])
{
dp[i][j][k]=tmp;
pre[i][j][k][0]=i;
pre[i][j][k][1]=j;
pre[i][j][k][2]=x;
}
}
if (dp[i][j][k]<inf)
{
qi.push(i);
qj.push(j);
inq[i][j]=1;
}
}
while (!qi.empty())
{
int ni=qi.front(),nj=qj.front();
qi.pop();qj.pop();
inq[ni][nj]=0;
F(i,0,3)
{
int ti=ni+mov[i][0],tj=nj+mov[i][1];
if (ti<=0||ti>n||tj<=0||tj>m) continue;
if (dp[ni][nj][k]+a[ti][tj]<dp[ti][tj][k])
{
dp[ti][tj][k]=dp[ni][nj][k]+a[ti][tj];
pre[ti][tj][k][0]=ni;
pre[ti][tj][k][1]=nj;
pre[ti][tj][k][2]=k;
if (!inq[ti][tj])
{
qi.push(ti);
qj.push(tj);
inq[ti][tj]=1;
}
}
}
}
}
F(i,1,n) F(j,1,m)
{
if (!a[i][j])
{
printf("%d\n",dp[i][j][(1<<cnt)-1]);
dfs(i,j,(1<<cnt)-1);
out();
return 0;
}
}
}