RE 求助

Exber @ 2021-08-04 08:38:46

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

#define S 1000005
#define MS 100005

using namespace std;

int n,m,stop[MS];
int esum,to[S],nxt[S],h[MS];
int ind[MS],lev[MS];
int ans;

inline void add(int x,int y)
{
    to[++esum]=y;
    nxt[esum]=h[x];
    h[x]=esum;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int s;
        scanf("%d",&s);
        for(int j=1;j<=s;j++)
        {
            scanf("%d",&stop[j]);
        }
        for(int j=stop[1];j<=stop[s];j++)
        {
            bool f=false;
            for(int k=1;k<=s;k++)
            {
                if(j==stop[k])
                {
                    f=true;
                    break;
                }
            }
            if(f)
            {
                continue;
            }
            for(int k=1;k<=s;k++)
            {
                add(j,stop[k]);
                ind[stop[k]]++;
            }
        }
    }
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        if(ind[i]==0)
        {
            q.push(i);
            lev[i]=1;
        }
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        ans=max(ans,lev[u]);
        for(int i=h[u];i;i=nxt[i])
        {
            int v=to[i];
            lev[v]=max(lev[v],lev[u]+1);
            if(!--ind[v])
            {
                q.push(v);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

by MatrixCascade @ 2021-08-04 08:47:02

@lovely_ckj 重边

by MattL @ 2021-08-04 08:47:56

红名刚学OI

by Exber @ 2021-08-04 08:50:02

@MatrixCascade 草？有重边吗？？？/jk/jk/jk

by MatrixCascade @ 2021-08-04 08:52:41

@lovely_ckj 就是连边改成这样

if(mp[j][stop[k]])continue;
                add(j,stop[k]);
                mp[j][stop[k]]=1;
                ind[stop[k]]++;

by Exber @ 2021-08-04 08:53:28

@MatrixCascade thx，我试试

by Exber @ 2021-08-04 08:56:52

谢谢，我过了 \^.^/

by 一只大龙猫 @ 2021-08-04 09:33:22

这是fAKe ckj的AC代码，我分享一下

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

#define S 1000005
#define MS 1005

using namespace std;

int n,m,stop[MS];
int esum,to[S],nxt[S],h[MS];
int ind[MS],lev[MS];
int ans;
bool vis[MS],hasadd[MS][MS];

inline void add(int x,int y)
{
    to[++esum]=y;
    nxt[esum]=h[x];
    h[x]=esum;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int s;
        scanf("%d",&s);
        memset(vis,0,sizeof(vis));
        for(int j=1;j<=s;j++)
        {
            scanf("%d",&stop[j]);
            vis[stop[j]]=true;
        }
        for(int j=stop[1];j<=stop[s];j++)
        {
            if(vis[j])
            {
                continue;
            }
            for(int k=1;k<=s;k++)
            {
                if(hasadd[j][stop[k]])
                {
                    continue;
                }
                hasadd[j][stop[k]]=true;
                add(j,stop[k]);
                ind[stop[k]]++;
            }
        }
    }
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        if(ind[i]==0)
        {
            q.push(i);
            lev[i]=1;
        }
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        ans=max(ans,lev[u]);
        for(int i=h[u];i;i=nxt[i])
        {
            int v=to[i];
            lev[v]=max(lev[v],lev[u]+1);
            if(!--ind[v])
            {
                q.push(v);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

by 一只大龙猫 @ 2021-08-04 09:33:54

@lovely_ckj

by 帅鹏 @ 2021-08-04 09:38:29

@lovely_ckj 重边

by Exber @ 2021-08-04 09:44:17

草