[关闭]
@ysner 2018-08-15T09:01:15.000000Z 字数 1879 阅读 2611

[HNOI2006]潘多拉的宝盒

图论


题面

给定个自动机,如果某个自动机能产生的所有串都能在自动机中产生(即走相同路径后,同时碰到输出元),则称的一个升级,求最长升级序列长度。

解析

辣鸡题目考语文
然而看懂题后还是很简单的。
判断是否为的升级,就每次分别在走相同的路径(因每个点有两个出度),若在碰到一个输出元,而此时没有,就说明不是升级。
是升级就把边权赋为
最后跑最长路即可。
(或者建边+拓扑排序也可以)。

但要注意,如果有两个完全相同的自动机,两者都会判为对方的升级,这时需强制只有一个方向边权赋为(建边的话跑缩点)。
没清空queue调了?h

  1. // luogu-judger-enable-o2
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<cmath>
  7. #include<algorithm>
  8. #include<queue>
  9. #define ll long long
  10. #define re register
  11. #define il inline
  12. #define max(a,b) ((a)>(b)?(a):(b))
  13. #define min(a,b) ((a)<(b)?(a);(b))
  14. #define N 100
  15. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  16. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  17. using namespace std;
  18. int s,n,m,h[N],out[N][N],a[N][N][2],dis[N][N];
  19. ll ans;
  20. bool vis[N][N];
  21. struct node{int x,y;};
  22. queue<node>Q;
  23. il int gi()
  24. {
  25. re int x=0,t=1;
  26. re char ch=getchar();
  27. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  28. if(ch=='-') t=-1,ch=getchar();
  29. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  30. return x*t;
  31. }
  32. il int check(re int s1,re int s2)
  33. {
  34. //printf("!!!%d %d\n",s1,s2);
  35. while(!Q.empty()) Q.pop();
  36. memset(vis,0,sizeof(vis));
  37. Q.push((node){1,1});
  38. while(!Q.empty())
  39. {
  40. re node now=Q.front(),tmp;Q.pop();//gg
  41. if(out[s1][now.x]&&!out[s2][now.y]) return 0;
  42. tmp.x=a[s1][now.x][0];tmp.y=a[s2][now.y][0];
  43. if(!vis[tmp.x][tmp.y]) vis[tmp.x][tmp.y]=1,Q.push(tmp);
  44. tmp.x=a[s1][now.x][1];tmp.y=a[s2][now.y][1];
  45. if(!vis[tmp.x][tmp.y]) vis[tmp.x][tmp.y]=1,Q.push(tmp);
  46. }
  47. return 1;
  48. }
  49. int main()
  50. {
  51. s=gi();
  52. fp(i,1,s)
  53. {
  54. n=gi();m=gi();
  55. //fp(j,1,n) a[i][j][0]=a[i][j][1]=1;
  56. fp(j,1,m) out[i][gi()+1]=1;
  57. fp(j,1,n)
  58. {
  59. re int u=gi()+1,v=gi()+1;
  60. a[i][j][0]=u;a[i][j][1]=v;
  61. }
  62. }
  63. memset(dis,-63,sizeof(dis));
  64. fp(i,1,s)
  65. fp(j,1,s)
  66. if(i!=j&&check(i,j)&&dis[j][i]<0) dis[i][j]=1;//注意到有完全相同的自动机
  67. //fp(i,1,s) fp(j,1,s) printf("%d %d %d\n",i,j,dis[i][j]);
  68. fp(k,1,s)
  69. fp(i,1,s)
  70. fp(j,1,s)
  71. //if(dis[i][j]<dis[i][k]+dis[k][j]&&dis[i][k]&&dis[k][j]
  72. dis[i][j]=max(dis[i][j],dis[i][k]+dis[k][j]),ans=max(ans,dis[i][j]);
  73. printf("%lld\n",ans+1);
  74. return 0;
  75. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注