这题不是拓扑吗
by hanjicheng @ 2018-09-28 17:06:55
@[hanjicheng](/space/show?uid=56986) 对啊，我上面写的就是拓扑
by info___tion @ 2018-09-28 17:07:38
刚刚把数据下了下来，发觉可能是读入的速度问题
by info___tion @ 2018-09-28 17:08:26
对不起，眼花了。
我再看一下代码
by hanjicheng @ 2018-09-28 17:09:35
我用的是深搜，你可以试试
by hanjicheng @ 2018-09-28 17:13:37
https://www.luogu.org/record/show?rid=4221254
by hanjicheng @ 2018-09-28 17:14:12
# register试试
by wxy_god @ 2018-09-28 17:16:16
@[我是一个垃圾](/space/show?uid=89396) 醒醒，都 8012 年了
by memset0 @ 2018-09-28 17:21:33
@[memset0](/space/show?uid=53495) 嗯
by wxy_god @ 2018-09-28 17:23:29
用了register,inline,更慢了……
```cpp
#include<stdio.h>
#define max(x,y) (x)>(y)?x:y
const int maxn=1002;
bool Map[maxn][maxn];
int a[maxn];
bool table[maxn];
struct edge
{
int to,val;
};
int head[maxn],Next[maxn*maxn];
edge G[maxn*maxn];
int sz;
inline void Insert(int from,edge e)
{
G[++sz]=e;
Next[sz]=head[from];
head[from]=sz;
return;
}
int dis[maxn];
int deg[maxn];
struct Qnode
{
int pos,val;
}que[2002];
int n;
inline void bfs()
{
for(int i=1;i<=n;i++)
dis[i]=1;
int h=0,t=0;
for(int i=1;i<=n;i++)
if(!deg[i]) que[t++]=(Qnode){i,1};
while( h^t )
{
Qnode H=que[h++];
h%=2001;
for(int i=head[H.pos];i;i=Next[i])
{
edge e=G[i];
deg[e.to]--;
if( !deg[e.to] )
{
dis[e.to]=H.val+1;
que[t++]=(Qnode){e.to,H.val+1};
t%=2001;
}
}
}
return;
}
inline int Read()
{
char c=getchar();
while( c<'0' or '9'<c ) c=getchar();
int res=0;
while( '0'<=c and c<='9' ) res=(res<<3)+(res<<1)+c-'0',c=getchar();
return res;
}
char buf[4];
int buf_sz;
inline void Write(int x)
{
buf_sz=0;
while(x>0) buf[buf_sz++]=x%10+'0',x/=10;
while( buf_sz-- ) putchar(buf[buf_sz]);
return;
}
int main(int argc, char const *argv[])
{
int m;
n=Read(),m=Read();
int l,r;
for(register int i=1;i<=m;i++)
{
if(i>1)
for(;l<=r;l++)
table[l]=false;
int len;
len=Read();
for(register int j=1;j<=len;j++)
{
a[j]=Read();
if(j==1) l=a[j];
else if(j==len) r=a[j];
table[a[j]]=true;
}
for(register int j=1;j<=len;j++)
for(register int k=l+1;k<r;k++)
{
if( a[j]==k or table[k] or Map[a[j]][k] ) continue;
Map[a[j]][k]=true;
Insert( a[j],(edge){k,1} );
deg[k]++;
}
}
bfs();
int ans=1;
for(register int i=1;i<=n;i++)
ans=max( ans,dis[i] );
Write(ans);
return 0;
}
```
这个比之前的慢了500多ms……
by info___tion @ 2018-09-28 17:32:29