题解 P2403 【[SDOI2010]所驼门王的宝藏】
YoungNeal
2018-06-01 22:02:27
题解在博客[食用](https://www.cnblogs.com/YoungNeal/p/9123725.html)效果更佳哦~
## Solution
一眼 $Tarjan$ 缩点拓扑求最长路。
然而如果直接暴力建边的话会$T$上天，因为这题要建的边贼多，比如说一行全是横门，暴力建边是两两之间都建的，最坏复杂度 $O(n^2)$。
考虑优化建图。
观察到一行的横门或者一列的纵门一定是在同一个连通分量里的，所以我们对于同一行的横门或者同一行的纵门就没必要两两连边了，保证直接连成一个环就好了。
但是如果一行中有很多横门，同时也有很多其他的门，那么还是会每个横门向每个别的种类的门连边，边数还是太多。
但是因为一行中的横门是一个环，所以对于一行中的其它宫室，只需从环上向这个宫室连一条边就够了。
于是得到了下面成型的算法思路：
我们对于每一行的横门，每一列的纵门，还有自由门分开建图。
第一遍建出横门向外连的所有边。第二遍建出纵门向外连的所有边。第三遍建出自由门向外连的所有边。
我们模拟第一次建边。
因为要优化建边过程的复杂度，我们想尽可能的先循环到横门，所以可以先排序一遍，这样的话如果当前不是横门就可以直接 $break$ 掉了。
对于所有宫室，我们按照行数排序，保证一行上的所有宫室都会一块循环到。如果行数相同，那么我们优先将横门排在前面。
对于循环到的每一行的第一个横门，我们将其记为 $first$，同时规定 $last$ 变量是上一个扫到的横门。
然后开始扫这一行的宫室。
如果当前宫室是横门，那么 $add(last,now)$,同时令 $last=now$。
否则，$add(last,now)$。
最后，$add(last,first)$。
这就完成了一行的扫描。
纵门也是同理。
对于自由门，我没有想出太好的建边方案，于是直接暴力枚举每个自由门周围的八个格子是否有宝藏。这里可以用 $STL$ 的 $map$ 来存储每个点是否有宝藏，但是我这里因为害怕被卡常，手写了个 $Hash$ 表。
其它就没什么了。
~~我还毒瘤的加上了fread快读~~
~~毒瘤的cnblogs说自由门是敏感词汇qwq~~
## Code
```cpp
#include<queue>
#include<cstdio>
#include<cctype>
#include<algorithm>
#define N 100005
#define mod 10007
#define ll long long
#define min(A,B) ((A)<(B)?(A):(B))
#define max(A,B) ((A)>(B)?(A):(B))
int x,n,m;
bool in[N];
int cnt,tot,sum;
int head2[N],deg[N];
std::queue<int> topo;
int stk[N],top,dis[N];
int head[N],belong[N];
int dfn[N],low[N],sze[N];
int hshhead[mod+2],hshcnt;
int dx[]={-1,0,1,0,1,1,-1,-1};
int dy[]={0,1,0,-1,1,-1,1,-1};
struct Edge{
int to,nxt;
}edge[N<<3],edge2[N<<3];
struct HASH{
ll data;
int nxt,idx;
}h[N<<2];
void hshadd(ll x,ll z,int i){
h[++hshcnt].data=z;
h[hshcnt].idx=i;
h[hshcnt].nxt=hshhead[x];
hshhead[x]=hshcnt;
}
struct Node{
int a,b,c,id;
}type[N];
bool cmp1(Node x,Node y){
if(x.a!=y.a) return x.a<y.a;
if(x.c==1) return 1;
if(y.c==1) return 0;
return x.b<y.b;
}
bool cmp2(Node x,Node y){
if(x.b!=y.b) return x.b<y.b;
if(x.c==2) return 1;
if(y.c==2) return 0;
return x.a<y.a;
}
void add(int x,int y){
edge[++cnt].to=y;
edge[cnt].nxt=head[x];
head[x]=cnt;
}
void add2(int x,int y){
edge2[++cnt].to=y;
edge2[cnt].nxt=head2[x];
head2[x]=cnt;
}
inline char nc(){
static const int BS=1<<22;
static unsigned char buf[BS],*st,*ed;
if(st==ed) ed=ed+fread(st=buf,1,BS,stdin);
return ed==st?EOF:*st++;
}
//#define nc getchar
inline int getint(){
int x=0;char ch;
while(!isdigit(ch=nc()));
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=nc();
return x;
}
void tarjan(int now){
dfn[now]=low[now]=++sum;
stk[++top]=now;in[now]=1;
for(int i=head[now];i;i=edge[i].nxt){
int to=edge[i].to;
if(!dfn[to]){
tarjan(to);
low[now]=min(low[now],low[to]);
}
else if(in[to])
low[now]=min(low[now],dfn[to]);
}
if(low[now]==dfn[now]){
int y;belong[now]=++tot;
do{
sze[tot]++;
y=stk[top--];
in[y]=0;
belong[y]=tot;
}while(y!=now);
}
}
void Hash(){
for(int i=1;i<=x;i++){
ll p=1LL*(type[i].a-1)*m+type[i].b;
ll q=p%mod;
hshadd(q,p,i);
}
}
int hsh(ll q){
ll p=q%mod;
for(int i=hshhead[p];i;i=h[i].nxt){
if(h[i].data==q)
return h[i].idx;
}
return 0;
}
signed main(){
x=getint(),n=getint(),m=getint();
for(int i=1;i<=x;i++){
type[i].a=getint();
type[i].b=getint();
type[i].c=getint();
type[i].id=i;
}
Hash();
std::sort(type+1,type+1+x,cmp1);
for(int i=1;i<=x;i++){
if(type[i].c==1){
int fina=0;
int fist,last=0;
for(int j=i;j<=x and type[i].a==type[j].a;j++){
fina=j;
if(type[i].c==type[j].c){
if(!last){
last=type[j].id;
fist=last;
continue;
}
add(last,type[j].id);
last=type[j].id;
}
else add(type[i].id,type[j].id);
}
if(last!=fist)
add(last,fist);
i=fina;
}
}
std::sort(type+1,type+1+x,cmp2);
for(int i=1;i<=x;i++){
if(type[i].c==2){
int fina=0;
int fist,last=0;
for(int j=i;j<=x and type[i].b==type[j].b;j++){
fina=j;
if(type[i].c==type[j].c){
if(!last){
last=type[j].id;
fist=type[j].id;
continue;
}
add(last,type[j].id);
last=type[j].id;
}
else add(type[i].id,type[j].id);
}
if(last!=fist)
add(last,fist);
i=fina;
}
}
for(int i=1;i<=x;i++){
for(int k=0;k<8;k++){
if(type[i].c!=3) continue;
int nx=type[i].a+dx[k];
int ny=type[i].b+dy[k];
int p=hsh(1LL*(nx-1)*m+ny);
if(!p)
continue;
add(type[i].id,p);
}
}
for(int i=1;i<=x;i++){
if(!dfn[i])
tarjan(i);
}
cnt=0;
for(int i=1;i<=x;i++){
for(int p=head[i];p;p=edge[p].nxt){
int to=edge[p].to;
if(belong[i]==belong[to]) continue;
deg[belong[to]]++;
add2(belong[i],belong[to]);
}
}
int ans=0;
for(int i=1;i<=tot;i++){
if(!deg[i]){
topo.push(i);
dis[i]=sze[i];
ans=max(ans,sze[i]);
}
}
while(topo.size()){
int u=topo.front();topo.pop();
for(int i=head2[u];i;i=edge2[i].nxt){
int to=edge2[i].to;
dis[to]=max(dis[to],dis[u]+sze[to]);
ans=max(ans,dis[to]);
deg[to]--;
if(!deg[to])
topo.push(to);
}
}
printf("%d\n",ans);
return 0;
}
```