总算理解了这个dp。

由于最后的结果一定成一个树形，
我们用dp[s][i]表示包括的关键点集合为s，当前树的根为i的最少花费。
转移有两种，一种是给树扩展一个节点，一种是把两棵树并在一起。
也就是:
1 dp[s][i]=dp[s][j]+a[i] j与i相邻
2 dp[s][i]=dp[x][i]+dp[s-x][i]-a[i] x为s的子集
从小到大枚举s
先做第一个转移 再用当前的s做第二个转移更新更大的s
由于第一个转移是有环的 我们要用spfa来实现

一ac就拿了bzoj rank1。。其实应该还有地方没有卡常。

#include<bits/stdc++.h>

const int S=1<<10,N=101,inf=1<<29;
int n,m,p,k,full;
int a[N],num[N],i,j,dy[12][12];

int fr[S][N],f[S][N];
int t[N];
struct edge
{
    int to,next;
}l[N<<2];int e;
void add_e(int x,int y)
{
    l[++e]=(edge){y,t[x]};t[x]=e;
    l[++e]=(edge){x,t[y]};t[y]=e;
}

int base;
int *g,*from;bool in[N];
int q[100000],head,tail,x,y;
void spfa()
{
    for(i=1;i<=p;++i) q[i]=i;
    tail=p;
    for(head=1;head<=tail;++head)
    {
        x=q[head];in[x]=0;
        for(i=t[x];y=l[i].to;i=l[i].next)
        if(g[y]>g[x]+a[y])
        {
            g[y]=g[x]+a[y];from[y]=base+x;
            if(!in[y]) {in[y]=1;q[++tail]=y;}
        }
    }
}

bool b[N];
void dfs(int s,int x)
{
    if(!s) return ;
    b[x]=1;
    int ns=fr[s][x]/N,y=fr[s][x]%N;
    if(y==x) {dfs(ns,x);dfs(s-ns,x);}
    else dfs(ns,y);
}

int main()
{
    freopen("1.in","r",stdin);freopen("1.out","w",stdout);
    scanf("%d%d",&n,&m);
    int i,j;
    for(i=1;i<=n;++i) 
    for(j=1;j<=m;++j) 
    {
     scanf("%d",a+(++p));
     dy[i][j]=p;
     if(!a[p])num[p]=++k;
    }

    full=(1<<k)-1;
    for(i=1;i<=full;++i)
    for(j=1;j<=p;++j)
     f[i][j]=inf;
    for(k=0,i=1;i<=p;++i)
    if(a[i]) f[0][i]=a[i];
    else f[1<<num[i]-1][i]=0;

    for(i=2;i<=n;++i) 
    for(j=1;j<=m;++j) 
     add_e(dy[i][j],dy[i-1][j]);
    for(j=2;j<=m;++j)
    for(i=1;i<=n;++i)
     add_e(dy[i][j-1],dy[i][j]);

    int s,ns;
    for(s=1;s<=full;++s)
    {
        g=f[s];from=fr[s];
        base=s*N;
        spfa();
        ns=full-s; 
        for(j=ns;j;j=(j-1)&ns)
        if(j<s)
        for(i=1;i<=p;++i)
         if(f[s+j][i]>g[i]+f[j][i]-a[i])
         {
             f[s+j][i]=g[i]+f[j][i]-a[i];
             fr[s+j][i]=base+i;
         }
    }

    int mn=1;
    for(i=2;i<=p;++i)
    if(g[i]<g[mn]) mn=i;
    printf("%d\n",g[mn]);
    dfs(full,mn);

    for(i=1;i<=n;puts(""),++i)
    for(j=1;j<=m;++j) 
    if(num[dy[i][j]]) printf("x"); else
    if(b[dy[i][j]]) printf("o"); else
    printf("_"); 
}