和普通的斯坦纳树不同，本题问的是最小的节点树。
因此在转移的时候将会有所不同。
当根节点为普通空地时，合并会导致根节点被重复计算一次，因此必须要把答案减一。
而若根节点为电器时，因为本身就不需要电线，所以不需要减一。
在松弛其他节点时，也可以通过BFS/SPFA来松弛，这样时间复杂度是近似$O(n^2)$的。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 int n,m,t; 8 char c[1001][1001]; 9 char s[1001]; 10 int f[55][55][1<<8]; 11 int dx[5]={0,1,-1,0,0}; 12 int dy[5]={0,0,0,1,-1}; 13 struct node 14 { 15 int x,y; 16 }; 17 queue<node>q; 18 int cnt; 19 int main() 20 { 21 cin>>n>>m>>t; 22 for(int i=1;i<=n;i++) 23 for(int j=1;j<=m;j++) 24 for(int k=0;k<=(1<<t)-1;k++) 25 f[i][j][k]=1e9; 26 for(int i=1;i<=n;i++) 27 { 28 cin>>(s+1); 29 for(int j=1;j<=m;j++) 30 { 31 c[i][j]=s[j]; 32 if(c[i][j]==‘+‘) 33 f[i][j][1<<(cnt++)]=1; 34 } 35 } 36 for(int k=0;k<=(1<<t)-1;k++) 37 { 38 for(int i=1;i<=n;i++) 39 for(int j=1;j<=m;j++) 40 { 41 if(c[i][j]==‘#‘)continue; 42 for(int l=k;l;l=(l-1)&k) 43 if(f[i][j][l]<1e9&&f[i][j][k-l]<1e9) 44 f[i][j][k]=min(f[i][j][k],f[i][j][l]+f[i][j][k^l]-1); 45 if(f[i][j][k]<1e9) 46 q.push((node){i,j}); 47 } 48 while(!q.empty()) 49 { 50 node tmp=q.front(); 51 q.pop(); 52 int x=tmp.x,y=tmp.y; 53 //cout<<"松弛"<<x<<" "<<y<<endl; 54 for(int i=1;i<=4;i++) 55 { 56 int xx=x+dx[i],yy=y+dy[i]; 57 if(c[xx][yy]!=‘#‘&&f[xx][yy][k]>f[x][y][k]+1) 58 { 59 f[xx][yy][k]=f[x][y][k]+1; 60 q.push((node){xx,yy}); 61 } 62 } 63 } 64 } 65 int ans=1e9; 66 //cout<<ends<<endl; 67 for(int i=1;i<=n;i++) 68 for(int j=1;j<=m;j++) 69 ans=min(ans,f[i][j][(1<<t)-1]); 70 cout<<ans-t; 71 72 } 73 /* 74 4 4 3 75 #..+ 76 +... 77 #... 78 +... 79 */