[关闭]
@ysner 2018-08-16T07:59:33.000000Z 字数 3165 阅读 1850

[SDOI2010]所驼门王的宝藏

图论 tarjan 缩点


题面

有一个的网格图,其中有个有门+宝藏的网格。这些门可以传送,且分为三类:

从任意点出发和终止,最多能经过多少有宝藏的网格。

解析

首先可以考虑到的一个问题是,建边不能达到
然而,如果门一都在同行,门二都在同列,就可以达到。
考虑把同行的门一、同列的门二用环连起来
这样效果等价(强连通),建边复杂度降到
然后再暴力连同行同列剩下的门(用环中的一点)和门三连的有宝藏网格即可。

这样弄完后,缩点+拓扑排序后跑最长路即可。(边权为联通块大小)

然而细节非常容易出锅:
1、如果中无值,访问
(其实最好把它当一般数组用)
2、不需要判
3、如果有两张图,且把搞混,就会莫名
4、如果使用判重结构体,需要重载运算符并手写函数。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<queue>
  8. #include<vector>
  9. #include<tr1/unordered_map>
  10. #define ll long long
  11. #define re register
  12. #define il inline
  13. #define max(a,b) ((a)>(b)?(a):(b))
  14. #define min(a,b) ((a)<(b)?(a):(b))
  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. const int N=1e5+100;
  19. struct Edge{int to,nxt;}e[N*50];
  20. struct node{int x,y,id;bool operator < (const node &o) const {return (x<o.x)||(x==o.x&&y<o.y);}}a[N];
  21. struct nnode{int x,y;bool operator == (const nnode &o) const {return x==o.x&&y==o.y;}}p[N*10];
  22. struct Hash{
  23. std::size_t operator () (const nnode &o) const{return o.x*N*10+o.y;};
  24. };
  25. int n,m,tot,h[N],cnt,fx[9]={0,1,-1,0,0,1,-1,1,-1},fy[9]={0,0,0,1,-1,1,-1,-1,1},low[N],dfn[N],st[N],tt,tim,sz[N],scc,bl[N],dis[N],T,in[N],ans,tmp[N];
  26. bool vis[N];
  27. vector<int>stan[N*10],stam[N*10];
  28. queue<int>Q;
  29. std::tr1::unordered_map<nnode,int,Hash>mp;
  30. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
  31. il int gi()
  32. {
  33. re int x=0,t=1;
  34. re char ch=getchar();
  35. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  36. if(ch=='-') t=-1,ch=getchar();
  37. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  38. return x*t;
  39. }
  40. il void tarjan(re int u)
  41. {
  42. low[u]=dfn[u]=++tim;vis[u]=1;st[++tt]=u;
  43. re int v;
  44. for(re int i=h[u];i+1;i=e[i].nxt)
  45. {
  46. v=e[i].to;
  47. if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
  48. else if(vis[v]) low[u]=min(low[u],dfn[v]);
  49. }
  50. if(low[u]==dfn[u])
  51. {
  52. ++scc;
  53. do{
  54. v=st[tt];vis[v]=0;bl[v]=scc;sz[scc]++;tt--;
  55. }
  56. while(v!=u);
  57. }
  58. }
  59. int main()
  60. {
  61. memset(h,-1,sizeof(h));
  62. tot=gi();n=gi();m=gi();
  63. fp(i,1,tot) a[i].x=gi(),a[i].y=gi(),a[i].id=gi(),mp[(nnode){a[i].x,a[i].y}]=i;
  64. fp(i,1,tot)
  65. {
  66. stan[a[i].x].push_back(i);
  67. stam[a[i].y].push_back(i);
  68. if(a[i].id==3)
  69. fp(j,1,8)
  70. {
  71. re int xx=a[i].x+fx[j],yy=a[i].y+fy[j];
  72. if(xx<1&&xx>n&&yy<1&&yy>m) continue;
  73. if(mp[(nnode){xx,yy}]) add(i,mp[(nnode){xx,yy}]);
  74. }
  75. }
  76. fp(i,1,n)
  77. {
  78. tt=0;
  79. for(re int j=0;j<stan[i].size();j++)
  80. if(a[stan[i][j]].id==1) tmp[++tt]=stan[i][j];
  81. fp(j,1,tt-1) add(tmp[j],tmp[j+1]);add(tmp[tt],tmp[1]);
  82. for(re int j=0;j<stan[i].size();j++)
  83. if(a[stan[i][j]].id!=1&&tt) add(tmp[1],stan[i][j]);
  84. }
  85. fp(i,1,m)
  86. {
  87. tt=0;
  88. for(re int j=0;j<stam[i].size();j++)
  89. if(a[stam[i][j]].id==2) tmp[++tt]=stam[i][j];
  90. fp(j,1,tt-1) add(tmp[j],tmp[j+1]);add(tmp[tt],tmp[1]);
  91. for(re int j=0;j<stam[i].size();j++)
  92. if(a[stam[i][j]].id!=2&&tt) add(tmp[1],stam[i][j]);
  93. }
  94. tt=0;
  95. fp(i,1,tot) if(!dfn[i]) tarjan(i);
  96. fp(u,1,tot)
  97. for(re int i=h[u];i+1;i=e[i].nxt)
  98. {
  99. re int v=e[i].to;
  100. if(bl[u]!=bl[v]) p[++T]=(nnode){bl[u],bl[v]};
  101. }
  102. memset(h,-1,sizeof(h));cnt=0;
  103. fp(i,1,T) add(p[i].x,p[i].y),in[p[i].y]++;
  104. fp(i,1,scc) if(!in[i]) Q.push(i);
  105. while(!Q.empty())
  106. {
  107. re int u=Q.front();Q.pop();dis[u]=max(dis[u],sz[u]);
  108. for(re int i=h[u];i+1;i=e[i].nxt)
  109. {
  110. re int v=e[i].to;--in[v];
  111. if(in[v]==0) Q.push(v);
  112. dis[v]=max(dis[v],dis[u]+sz[v]);
  113. ans=max(ans,dis[v]);
  114. }
  115. }
  116. printf("%d\n",ans);
  117. return 0;
  118. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注