拓扑排序40pts求助!

P1983 [NOIP2013 普及组] 车站分级

Fat_Fish @ 2021-08-05 16:11:25

rt,评测记录,实在不知道哪里错了

#include<bits/stdc++.h>
#define max(a,b) (a)>(b)?(a):(b)
using namespace std;
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)) {
        if(ch=='-') {
            f=-1;
        }
        ch=getchar();
    }
    while(isdigit(ch)) {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
const int maxn=1e3+10;
int n,m,ind[maxn],a[maxn],d[maxn],ans,P[maxn];
vector<int> g[maxn];
void topo(){
    queue<int> q;
    for(int i=1;i<=n;++i){
        if(ind[i]==0){
            q.push(i);
            d[i]=1;
        }
    }
    while(!q.empty()){
        int u=q.front();q.pop();
        int len=g[u].size();
        for(int i=0;i<len;++i){
            int v=g[u][i];
            d[v]=max(d[v],d[u]+1);
            --ind[v];
            if(ind[v]==0){
                q.push(v);
            }
        }
    } 
    for(int i=1;i<=n;++i){
        ans=max(ans,d[i]);
    }
    return;
}
signed main() {
    n=read(),m=read();
    while(m--){
        memset(P,0,sizeof P);
        int k;
        k=read();
        for(int i=1;i<=k;++i){
            a[i]=read();
            P[a[i]]=1;
        }
        for(int i=a[1];i<=a[k];++i){
            if(P[i]==0){
                continue;
            }
            for(int j=i+1;j<=a[k];++j){
                if(P[j]==0){
                    g[j].push_back(i);//j比i小 
                    ++ind[i];
                }
            }
        } 
    }
    topo();
    printf("%d\n",ans);
    return 0;
}

by Sudohry @ 2021-08-05 16:16:49

MLE也许是因为连边太多vector出问题了吧

换邻接表试一下?


by Fat_Fish @ 2021-08-05 16:18:06

可是还有WA的几个点,不知道是怎么回事QAQ


by Fat_Fish @ 2021-08-05 16:28:16

原来是我题目没看清,谢谢大佬


by Sudohry @ 2021-08-05 16:30:28

@Fat_Fish 哦我想起来了你那个MLE可能是有重边,记得判重(我也是vector党)

wa我还没看出来


by Fat_Fish @ 2021-08-05 16:36:07

没事,WA已经改了,谢谢


by Fat_Fish @ 2021-08-05 16:37:27

已经AC了


|