設$f[i][j][k]$表示從房間$j$的第$k$扇門進去探索不超過$i$步的情況。

對于$0$步的情況，可以用每個房間的度數來表示。

否則可以繞著那個房間走一圈，將所有情況依次hash來表示。

最后對于每個房間求出$f$的最小表示，即可完成hash。

時間復雜度$O(n^4)$。

?

#include<cstdio> #include<vector> #include<algorithm> using namespace std; typedef unsigned long long ll; const int N=105; int n,m,i,j,k,t,o,x,d[N],a[N][N],b[N][N],q[N];ll f[2][N][N]; vector<ll>g[N];vector<int>ans[N]; inline bool cmp(int x,int y){return g[x]==g[y]?x<y:g[x]<g[y];} int main(){scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&d[i]);for(j=1;j<=d[i];j++)scanf("%d",&a[i][j]),b[i][a[i][j]]=j;}for(i=1;i<=n;i++)for(j=1;j<=d[i];j++)f[0][i][j]=d[i]+1;for(i=1;i<=n;i++){o^=1;for(j=1;j<=n;j++)for(k=1;k<=d[j];k++){f[o][j][k]=f[o^1][j][k]*10007+13331;x=a[j][k];for(t=b[x][j];t<=d[x];t++)f[o][j][k]=f[o][j][k]*233+f[o^1][x][t];for(t=1;t<b[x][j];t++)f[o][j][k]=f[o][j][k]*233+f[o^1][x][t];}}for(i=1;i<=n;i++){for(j=1;j<=d[i];j++)g[i].push_back(f[o][i][j]);for(j=2;j<=d[i];j++){vector<ll>h;for(k=j;k<=d[i];k++)h.push_back(f[o][i][k]);for(k=1;k<j;k++)h.push_back(f[o][i][k]);g[i]=max(g[i],h);}g[i].push_back(d[i]);q[i]=i;}sort(q+1,q+n+1,cmp);for(i=1;i<=n;i=j){for(j=i;j<=n&&g[q[i]]==g[q[j]];j++);if(i+1==j)continue;for(m++,k=i;k<j;k++)ans[m].push_back(q[k]);}if(!m)puts("none");else{sort(ans+1,ans+m+1);for(i=1;i<=m;i++){printf("%d",ans[i][0]);for(j=1;j<ans[i].size();j++)printf(" %d",ans[i][j]);puts("");}}return 0; }

　　

轉載于:https://www.cnblogs.com/clrs97/p/6651278.html

總結

以上是生活随笔為你收集整理的BZOJ4076 : [Wf2014]Maze Reduction的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。