MLE两个点！！求助

zcayyds @ 2021-09-04 21:51:11

#include<bits/stdc++.h>
using namespace std;
long long ans=INT_MIN,n,m,s[1005],f[1005],in[1005],out[1005];
vector<int> p[1005];
bool is[1005];
queue<int>q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        memset(is,0,sizeof(is));
        cin>>s[0];
        for(int j=1;j<=s[0];j++)
            cin>>s[j],is[s[j]]=1;
        for(int k=s[1];k<=s[s[0]];k++)
            if(!is[k])
                for(int u=1;u<=s[0];u++)
                    p[s[u]].push_back(k),in[k]++,out[s[u]]++;
    }
    for(int i=1;i<=n;i++)
        if(!in[i])q.push(i),f[i]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=0;i<p[x].size();i++){
            int y=p[x][i];
            f[y]=f[x]+1;
            in[y]--;
            if(in[y]==0)q.push(y);
        }
    }
    for(int i=1;i<=n;i++)ans=max(ans,f[i]);
    cout<<ans;
    return 0;
}

by Trafford1894 @ 2021-09-05 21:30:45

很明显重边了，加一个 \text{vis} 数组判重

by Trafford1894 @ 2021-09-05 21:32:28

@hsemshn_hyg 改成这样就 AC 了

#include<bits/stdc++.h>
using namespace std;
long long ans=INT_MIN,n,m,s[1005],f[1005],in[1005],out[1005],vis[1005][1005];
vector<int> p[1005];
bool is[1005];
queue<int>q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        memset(is,0,sizeof(is));
        cin>>s[0];
        for(int j=1;j<=s[0];j++)
            cin>>s[j],is[s[j]]=1;
        for(int k=s[1];k<=s[s[0]];k++)
            if(!is[k])
                for(int u=1;u<=s[0];u++)
                    if(!vis[k][s[u]])p[s[u]].push_back(k),in[k]++,out[s[u]]++,vis[k][s[u]]=1;//在这一行有改动
    }
    for(int i=1;i<=n;i++)
        if(!in[i])q.push(i),f[i]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=0;i<p[x].size();i++){
            int y=p[x][i];
            f[y]=f[x]+1;
            in[y]--;
            if(in[y]==0)q.push(y);
        }
    }
    for(int i=1;i<=n;i++)ans=max(ans,f[i]);
    cout<<ans;
    return 0;
}

by zcayyds @ 2021-09-07 21:09:18

谢谢

by zcayyds @ 2021-09-07 21:09:40

大佬