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

差不多是斯坦纳树裸题，不过边权化成了点权，这样在合并两棵子树时需要去掉根结点的权值，防止重复。
题目还要求输出解，只要在转移时记录下路径，然后dfs一遍就好了。
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=10+2,inf=0x3f3f3f3f;
 5 const int dx[]= {0,0,-1,1};
 6 const int dy[]= {-1,1,0,0};
 7 int n,m,k,dp[1<<10][N][N],a[N][N],inq[N][N];
 8 char s[N][N];
 9 struct D {int x,y;} X[N];
10 struct Ans {int S,x,y;} ansS,nxt[1<<10][N][N];
11 queue<D> q;
12 void upd(int x,int y,int c,int S,int x2,int y2) {
13     if(dp[S][x][y]>c) {
14         dp[S][x][y]=c;
15         nxt[S][x][y]= {S,x2,y2};
16         if(!inq[x][y])inq[x][y]=1,q.push({x,y});
17     }
18 }
19 void spfa(int S) {
20     while(q.size())q.pop();
21     memset(inq,0,sizeof inq);
22     for(int i=1; i<=n; ++i)
23         for(int j=1; j<=m; ++j)
24             if(dp[S][i][j]!=inf)inq[i][j]=1,q.push({i,j});
25     while(q.size()) {
26         int x=q.front().x,y=q.front().y;
27         q.pop(),inq[x][y]=0;
28         for(int i=0; i<4; ++i) {
29             int x2=x+dx[i],y2=y+dy[i];
30             if(x2<1||x2>n||y2<1||y2>m)continue;
31             upd(x2,y2,dp[S][x][y]+a[x2][y2],S,x,y);
32         }
33     }
34 }
35 void dfs(int S,int x,int y) {
36     if(!a[x][y])s[x][y]='x';
37     else s[x][y]='o';
38     int S2=nxt[S][x][y].S,x2=nxt[S][x][y].x,y2=nxt[S][x][y].y;
39     if(!S2)return;
40     else if(S2==S)dfs(S2,x2,y2);
41     else dfs(S2,x2,y2),dfs(S^S2,x2,y2);
42 }
43 int main() {
44     scanf("%d%d",&n,&m);
45     for(int i=1; i<=n; ++i)
46         for(int j=1; j<=m; ++j) {
47             scanf("%d",&a[i][j]);
48             if(!a[i][j])X[k++]= {i,j};
49         }
50     memset(dp,inf,sizeof dp);
51     for(int i=0; i<k; ++i)dp[1<<i][X[i].x][X[i].y]=a[X[i].x][X[i].y];
52     for(int S=1; S<(1<<k); ++S) {
53         for(int S2=(S-1)&S; S2; S2=(S2-1)&S)
54             for(int i=1; i<=n; ++i)
55                 for(int j=1; j<=m; ++j) {
56                     dp[S][i][j]=min(dp[S][i][j],dp[S2][i][j]+dp[S^S2][i][j]-a[i][j]);
57                     if(dp[S][i][j]==dp[S2][i][j]+dp[S^S2][i][j]-a[i][j])nxt[S][i][j]= {S2,i,j};
58                 }
59         spfa(S);
60     }
61     int ans=inf;
62     for(int i=1; i<=n; ++i)
63         for(int j=1; j<=m; ++j) {
64             ans=min(ans,dp[(1<<k)-1][i][j]);
65             if(ans==dp[(1<<k)-1][i][j])ansS= {(1<<k)-1,i,j};
66         }
67     for(int i=1; i<=n; ++i)
68         for(int j=1; j<=m; ++j)s[i][j]='_';
69     dfs(ansS.S,ansS.x,ansS.y);
70     printf("%d
",ans);
71     for(int i=1; i<=n; ++i) {
72         for(int j=1; j<=m; ++j)putchar(s[i][j]);
73         puts("");
74     }
75     return 0;
76 }