Description
Input
Output
输出一个整数，为矿工获得所有宝藏的最小代价。
Sample Input
2 2 2
10 9
10 10
10 1
10 10
1 1 1
1 2 2
Solution
斯坦纳树
可以先考虑二维的
由于k只有9，状压
设f[x,y,s]表示（树根）在点（x,y），关键点的选取情况至少为s，的最优答案
有两种转移方式
1.这种没有后效性
f[x,y,s]min=f[x,y,s′]+f[x,y,s−s′]−a[x,y](s′∈s)
2.有后效性
f[x,y,s]min=f[x′,y′,s]+a[x,y]((x′,y′)与(x,y)四联通)
有后效性怎么办?
用SPFA就可以解决问题
那么转移时先从小到大枚举s，再枚举x,y，然后先进行第一种转移，再进行第二种转移
三维的时候就把多个二维拼到一起
一种简单的方式就是对于每一层新建一个关键点，代表是否与下面那一层的值加了起来
初始化时就把所有关键点处理好，和所有非关键点也处理好，因为状态s表示的是至少为s，所以不会错
在打题时如果调试过的话，也许能更好的理解
Code
#include<cstdio>#include<cstring>#define fo(i,a,b) for(int i=a;i<=b;i++)#define fd(i,a,b) for(int i=a;i>=b;i--)#define N 15#define ll long longusing namespace std;int a[N][N][N],f[N][N][N][1024],e[N],d[N*N][2],b[N],c[N][N][2],tr[N][N][N],h,n,m,bz[N][N];int fx[4][2]={{1,0},{0,1},{-1,0},{0,-1}};int main(){ freopen("treasure.in","r",stdin); freopen("treasure.out","w",stdout); e[0]=1;fo(i,1,11) e[i]=e[i-1]*2; scanf("%d%d%d",&h,&n,&m); fo(i,1,h) {fo(j,1,n) {fo(k,1,m) {scanf("%d",&a[i][j][k]);fo(s,0,e[11]-1) f[i][j][k][s]=214748347; } } } fo(i,1,h) {scanf("%d",&b[i]); fo(j,1,b[i]) {scanf("%d%d",&c[i][j][0],&c[i][j][1]); tr[i][c[i][j][0]][c[i][j][1]]=j; } } fd(i,h,1) {fo(x,1,n) fo(y,1,m) {f[i][x][y][e[b[i]]]=f[i+1][x][y][e[b[i+1]+1]-1]+a[i][x][y]; f[i][x][y][0]=a[i][x][y]; } fo(j,1,b[i]) f[i][c[i][j][0]][c[i][j][1]][e[j-1]]=a[i][c[i][j][0]][c[i][j][1]]; fo(s,1,e[b[i]+1]-1) {fo(x,1,n) fo(y,1,m) {fo(s1,1,s)if((s & s1)==s1){if(f[i][x][y][s1]+f[i][x][y][s-s1]-a[i][x][y]<f[i][x][y][s]) f[i][x][y][s]=f[i][x][y][s1]+f[i][x][y][s-s1]-a[i][x][y];}memset(bz,0,sizeof(bz));int q=0,w=1;d[1][0]=x;d[1][1]=y;while(q<w){q++;fo(k,0,3){int x1=d[q][0]+fx[k][0],y1=d[q][1]+fx[k][1]; if(x1>0&&y1>0&&x1<=n&&y1<=m&&f[i][x1][y1][s]>f[i][d[q][0]][d[q][1]][s]+a[i][x1][y1]) {f[i][x1][y1][s]=f[i][d[q][0]][d[q][1]][s]+a[i][x1][y1]; if(!bz[x1][y1]) {bz[x1][y1]=1;d[++w][0]=x1;d[w][1]=y1; } }}bz[d[q][0]][d[q][1]]=0;} } } } int ans=2147483647; fo(x,1,n) fo(y,1,m) if(f[1][x][y][e[b[1]+1]-1]<ans) ans=f[1][x][y][e[b[1]+1]-1]; printf("%d",ans);}
