P4294 [WC2008]游览计划 (斯坦纳树)

题目链接

差不多是斯坦纳树裸题，不过边权化成了点权，这样在合并两棵子树时需要去掉根结点的权值，防止重复。

题目还要求输出解，只要在转移时记录下路径，然后dfs一遍就好了。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=+,inf=0x3f3f3f3f;

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

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

 int n,m,k,dp[<<][N][N],a[N][N],inq[N][N];

 char s[N][N];

 struct D {int x,y;} X[N];

 struct Ans {int S,x,y;} ansS,nxt[<<][N][N];

 queue<D> q;

 void upd(int x,int y,int c,int S,int x2,int y2) {

     if(dp[S][x][y]>c) {

         dp[S][x][y]=c;

         nxt[S][x][y]= {S,x2,y2};

         if(!inq[x][y])inq[x][y]=,q.push({x,y});

     }

 }

 void spfa(int S) {

     while(q.size())q.pop();

     memset(inq,,sizeof inq);

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

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

             if(dp[S][i][j]!=inf)inq[i][j]=,q.push({i,j});

     while(q.size()) {

         int x=q.front().x,y=q.front().y;

         q.pop(),inq[x][y]=;

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

             int x2=x+dx[i],y2=y+dy[i];

             if(x2<||x2>n||y2<||y2>m)continue;

             upd(x2,y2,dp[S][x][y]+a[x2][y2],S,x,y);

         }

     }

 }

 void dfs(int S,int x,int y) {

     if(!a[x][y])s[x][y]='x';

     else s[x][y]='o';

     int S2=nxt[S][x][y].S,x2=nxt[S][x][y].x,y2=nxt[S][x][y].y;

     if(!S2)return;

     else if(S2==S)dfs(S2,x2,y2);

     else dfs(S2,x2,y2),dfs(S^S2,x2,y2);

 }

 int main() {

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

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

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

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

             if(!a[i][j])X[k++]= {i,j};

         }

     memset(dp,inf,sizeof dp);

     for(int i=; i<k; ++i)dp[<<i][X[i].x][X[i].y]=a[X[i].x][X[i].y];

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

         for(int S2=(S-)&S; S2; S2=(S2-)&S)

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

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

                     dp[S][i][j]=min(dp[S][i][j],dp[S2][i][j]+dp[S^S2][i][j]-a[i][j]);

                     if(dp[S][i][j]==dp[S2][i][j]+dp[S^S2][i][j]-a[i][j])nxt[S][i][j]= {S2,i,j};

                 }

         spfa(S);

     }

     int ans=inf;

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

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

             ans=min(ans,dp[(<<k)-][i][j]);

             if(ans==dp[(<<k)-][i][j])ansS= {(<<k)-,i,j};

         }

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

         for(int j=; j<=m; ++j)s[i][j]='_';

     dfs(ansS.S,ansS.x,ansS.y);

     printf("%d\n",ans);

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

         for(int j=; j<=m; ++j)putchar(s[i][j]);

         puts("");

     }

     return ;

 }