腊鸡题目，实在卡不过去。
（改了一下午）
就是裸的斯坦纳树的题目，一方面合并子集，另一方面SPFA迭代求解。
优化了许多地方，甚至基数排序都写了。
还是T到死，，不打算改了，就这样吧
#include <map> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define F(i,j,k) for (int i=j;i<=k;++i) #define D(i,j,k) for (int i=j;i>=k;--i) #define inf 0x3f3f3f3f #define maxn 502 #define ll long long #define mp make_pair short n,r,c,a[maxn][maxn]; int dp[maxn][maxn][10][10]; char s[maxn][maxn]; short mov[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; short go[maxn][maxn][4][2]; void Readin() { memset(dp,0x3f,sizeof dp); cin>>n>>c>>r; F(i,1,r) { scanf("%s",s[i]+1); F(j,1,c) { switch(s[i][j]) { case ‘.‘:a[i][j]=0;break; case ‘x‘:a[i][j]=-1;break; case ‘A‘:a[i][j]=10;break; case ‘C‘:a[i][j]=11;break; default: a[i][j]=s[i][j]-‘0‘;dp[i][j][a[i][j]][a[i][j]]=0;break; } } } F(i,0,r) a[i][0]=a[i][c+1]=-1;F(i,0,c) a[0][i]=a[r+1][i]=-1; a[r+1][c+1]=-1; } int vis[maxn][maxn][4],idx; void dfs(int nx,int ny,int k) { int tmp=k; if (vis[nx][ny][k]==idx) { go[nx][ny][k][0]=-1; go[nx][ny][k][1]=-1; return; } vis[nx][ny][k]=idx; if (go[nx][ny][k][0]!=0) return; switch(a[nx][ny]) { case 10:tmp=(tmp+3)%4;break; case 11:tmp=(tmp+1)%4;break; } if (a[nx+mov[tmp][0]][ny+mov[tmp][1]]==-1) { go[nx][ny][k][0]=nx; go[nx][ny][k][1]=ny; return; } int tx=nx+mov[tmp][0],ty=ny+mov[tmp][1]; if (!go[tx][ty][tmp][0]) dfs(tx,ty,tmp); go[nx][ny][k][0]=go[tx][ty][tmp][0]; go[nx][ny][k][1]=go[tx][ty][tmp][1]; } void init() { F(i,1,r) F(j,1,c) F(k,0,3){ int nx=i,ny=j,flag=1;++idx; dfs(nx,ny,k); } } struct Statement{short x,y,l,r; int v;}sta[maxn*maxn],res[maxn*maxn]; queue <Statement> q,d; int top=0; bool Com(Statement a, Statement b) {return a.v<b.v;} int cnt[200005],ctop=0; void Radix_Sort() { memset(cnt,0,sizeof cnt); F(i,1,top) { if (sta[i].v>=200000) continue; cnt[sta[i].v]++,ctop=max(ctop,sta[i].v); } F(i,1,ctop) cnt[i]+=cnt[i-1]; int tmp=cnt[ctop]; F(i,1,top) { if (sta[i].v>=200000) continue; res[cnt[sta[i].v]--]=sta[i]; } F(i,1,tmp) sta[i]=res[i]; memcpy(sta,res,(top+1)*sizeof(Statement)); } void SPFA() { // sort(sta+1,sta+top+1,Com); Radix_Sort(); F(i,1,top) q.push(sta[i]); while (!q.empty()||!d.empty()) { int nx,ny,l,r,v; if (d.empty()||(!d.empty()&&!q.empty()&&q.front().v<=d.front().v)) { Statement now=q.front(); q.pop(); nx=now.x,ny=now.y,l=now.l,r=now.r,v=now.v; } else { Statement now=d.front(); d.pop(); nx=now.x,ny=now.y,l=now.l,r=now.r,v=now.v; } if (dp[nx][ny][l][r]<v) continue; for (int k=0;k<4;++k) if (go[nx][ny][k][0]!=-1) { int tx=go[nx][ny][k][0],ty=go[nx][ny][k][1]; if (dp[tx][ty][l][r]>dp[nx][ny][l][r]+1) { dp[tx][ty][l][r]=dp[nx][ny][l][r]+1; Statement now; now.x=tx;now.y=ty;now.l=l;now.r=r;now.v=dp[tx][ty][l][r]; d.push(now); } } } } void DP() { F(i,1,r) F(j,1,c) if (a[i][j]>=1&&a[i][j]<=n) {++top;sta[top].x=i;sta[top].y=j;sta[top].l=a[i][j];sta[top].r=a[i][j];sta[top].v=dp[i][j][a[i][j]][a[i][j]];} SPFA(); F(len,2,n) { F(i,1,n-len+1) { top=0; int j=i+len-1; F(x,1,r) F(y,1,c) { F(z,i,j-1) dp[x][y][i][j]=min(dp[x][y][i][z]+dp[x][y][z+1][j],dp[x][y][i][j]); if (dp[x][y][i][j]<inf) { Statement now; now.x=x;now.y=y;now.l=i;now.r=j;now.v=dp[x][y][i][j]; sta[++top]=now; } } SPFA(); } } int ans=inf; F(i,1,r) F(j,1,c) ans=min(ans,dp[i][j][1][n]); printf("%d\n",ans==inf?-1:ans); } int main() { Readin(); init(); DP(); }
BZOJ 3205 [Apio2013]机器人 ——斯坦纳树