[模板] 斯坦纳树

野性酷女 2023-08-17 17:16 93阅读 0赞

## 斯坦纳树 ##

斯坦纳树解决的是这样的一类问题:

在有边权/点权无向图上找到总权值最小的子图, 使得给定的关键点互相连通.

容易发现得到的子图会是一棵树.

//to upd

## 代码 ##

//luogu4294 [WC2008]游览计划
    #include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<set>
    #include<map>
    #include<queue>
    #include<vector>
    using namespace std;
    #define rep(i,l,r) for(register int i=(l);i<=(r);++i)
    #define repdo(i,l,r) for(register int i=(l);i>=(r);--i)
    #define il inline
    typedef double db;
    typedef long long ll;
    
    //---------------------------------------
    const int nsz=15,psz=150,k2sz=1050,ninf=1e3;
    int n,m,k,bnd,val[nsz][nsz],isedge[nsz][nsz],choose[nsz][nsz];
    int dir[5][2]{
        {1,0},{-1,0},{0,1},{0,-1}};
    
    int dp[k2sz][nsz][nsz];
    
    struct tpl{int x,y;}emp[nsz];
    struct tdis{tpl p;int d;};
    bool operator<(const tdis &a,const tdis &b){return a.d>b.d;}
    priority_queue<tdis> pq;
    int curs;
    
    pair<int,tpl> pre[k2sz][nsz][nsz];
    int vi[nsz][nsz];
    void dij(){
        rep(i,1,n)rep(j,1,m)vi[i][j]=0;
        int cnt=0,cntt=n*m,d;
        tpl u;
        while(!pq.empty()&&cnt<cntt){
            u=pq.top().p,d=pq.top().d,pq.pop();
            if(vi[u.x][u.y])continue;
            vi[u.x][u.y]=1,++cnt;
            rep(i,0,3){
                int x1=u.x+dir[i][0],y1=u.y+dir[i][1];
                int tmp=val[x1][y1]+d;
                if(!isedge[x1][y1]&&dp[curs][x1][y1]>tmp){
                    dp[curs][x1][y1]=tmp;
                    pre[curs][x1][y1]=make_pair(curs,(tpl){u.x,u.y});
                    pq.push((tdis){(tpl){x1,y1},tmp});
                }
            }
        }
    }
    
    void dfs(int p,int x,int y){
        if(p==0)return;
        choose[x][y]=1;
        auto tmp=pre[p][x][y];
        dfs(tmp.first,tmp.second.x,tmp.second.y);
        if(tmp.first&&tmp.first!=p)dfs(p^tmp.first,tmp.second.x,tmp.second.y);
    }
    
    int sol(){
        bnd=(1<<k)-1;
        rep(i,1,bnd)rep(a,1,n)rep(b,1,m)dp[i][a][b]=ninf;
        rep(i,1,k)dp[1<<(i-1)][emp[i].x][emp[i].y]=0;
        rep(i,1,bnd){
            curs=i;
            priority_queue<tdis>().swap(pq);
            rep(a,1,n){
                rep(b,1,m){
                    int &cur=dp[i][a][b];
                    for(int j=(i-1)&i;j;j=(j-1)&i){
                        int tmp=dp[j][a][b]+dp[i^j][a][b]-val[a][b];
                        if(cur>tmp)cur=tmp,pre[i][a][b]=make_pair(j,(tpl){a,b});
                    }
                    if(cur<ninf)pq.push((tdis){(tpl){a,b},cur});
                }
            }
    //      printf("s=%d\n",i);
    //      rep(a,1,n){
    //          rep(b,1,m)printf("%d ",dp[i][a][b]);
    //          printf("\n");
    //      }
    //      printf("\n");
            dij();
    //      printf("res\n");
    //      rep(a,1,n){
    //          rep(b,1,m)printf("%d ",dp[i][a][b]);
    //          printf("\n");
    //      }
    //      printf("\n");
    //      printf("pre\n");
    //      rep(a,1,n){
    //          rep(b,1,m)printf("<%d %d %d> ",pre[i][a][b].first,pre[i][a][b].second.x,pre[i][a][b].second.y);
    //          printf("\n");
    //      }
    //      printf("\n");
    
        }
        int res=ninf,resx,resy;
        rep(i,1,n)rep(j,1,m)if(dp[bnd][i][j]<res)res=dp[bnd][i][j],resx=i,resy=j;
        dfs(bnd,resx,resy);
        return res;
    }
    
    int main(){
        ios::sync_with_stdio(0),cin.tie(0);
        cin>>n>>m;
        rep(i,0,n+1)isedge[i][0]=isedge[i][m+1]=1;
        rep(i,1,m)isedge[0][i]=isedge[n+1][i]=1;
        rep(i,1,n){
            rep(j,1,m){
                cin>>val[i][j];
                if(val[i][j]==0)emp[++k]=(tpl){i,j};
            }
        }
        cout<<sol()<<'\n';
        rep(i,1,n){
            rep(j,1,m){
                if(val[i][j]==0)cout<<'x';
                else if(choose[i][j])cout<<'o';
                else cout<<'_';
            }
            cout<<'\n';
        }
        return 0;
    }

转载于:https://www.cnblogs.com/ubospica/p/11166696.html