info___tion @ 2018-09-28 17:02:06

#include<stdio.h>
#include<string.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;

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[10002];

int n;

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%=10001;

        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%=10001;
            }
        }
    }

    return;
}

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[10];
int buf_sz;

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();

    for(int i=1;i<=m;i++)
    {
        memset( table,false,sizeof(table) );

        int len;
        len=Read();

        int l,r;

        for(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(int j=1;j<=len;j++)
            for(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(int i=1;i<=n;i++)
        ans=max( ans,dis[i] );

    Write(ans);

    return 0;
}

by hanjicheng @ 2018-09-28 17:06:55

这题不是拓扑吗

by info___tion @ 2018-09-28 17:07:38

@hanjicheng 对啊，我上面写的就是拓扑

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

我用的是深搜，你可以试试

by hanjicheng @ 2018-09-28 17:14:12

https://www.luogu.org/record/show?rid=4221254

by wxy_god @ 2018-09-28 17:16:16

register试试

by memset0 @ 2018-09-28 17:21:33

@我是一个垃圾 醒醒，都 8012 年了

by wxy_god @ 2018-09-28 17:23:29

@memset0 嗯

by info___tion @ 2018-09-28 17:32:29

用了register,inline,更慢了……

#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……