10pts求助

P1983 [NOIP2013 普及组] 车站分级

Kniqht @ 2023-07-16 09:46:28

这个代码就是加入一个虚拟原点后进行topsort(减少了建图的复杂度)

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<utility>
#include<algorithm>
#define ll long long
using namespace std;
const int N=2e6+10,M=2010,inf=0x3f3f3f3f;
int n,m,a[M],s[M];
bool st[M];
int g[M][M],d[M];
void add(int a,int b,int c){
    if(g[a][b]!=inf) return;
    g[a][b]=c;
//  e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
    d[b]++;
}
int q[N];
int topsort(){
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++)
        if(!d[i]) q[++tt]=i,s[i]=1;
    while(hh<=tt){
        int t=q[hh++];
        for(int i=1;i<=n+m;i++){
            if(g[t][i]!=inf&&--d[i]==0){
                q[++tt]=i;
                s[i]=s[t]+g[t][i];
            }
        } 
    } 
    int ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,s[i]);
    return ans;
}
signed main(){
    memset(g,0x3f,sizeof(g));
    scanf("%d%d",&n,&m);int t;
    for(int T=1;T<=m;T++){
        memset(st,0,sizeof(st));
        scanf("%d",&t);
        for(int i=1;i<=t;i++) scanf("%d",&a[i]),st[a[i]]=true;
        for(int i=a[1];i<=a[t];i++)
            if(!st[i])
                add(i,T+n,1);
        for(int i=1;i<=t;i++) add(T+n,a[i],0);
    }
    printf("%d",topsort());
    return 0;
}

这个是不加虚拟原点,以前写的代码能AC(虽然感觉建图时间复杂度是有问题的)

#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=N*N;
int n,m;
int q[N],d[N],g[N],p[N];
bool st[N],isIn[N][N];
int topsort(){
    int hh=0,tt=-1,res=0;
    for(int i=1;i<=n;i++)
        if(!d[i]){
            q[++tt]=i;
            p[i]=1;
        }
    while(hh<=tt){
        int t=q[hh++];
        for(int j=1;j<=n;j++){
            if(!isIn[t][j]) continue;
            if(--d[j]==0){
                q[++tt]=j;
                p[j]=p[t]+1;
            }
        }
    }
    for(int i=1;i<=n;i++)
        res=max(res,p[i]);
    return res;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        memset(st,0,sizeof(st));
        int t;
        cin>>t;
        for(int j=1;j<=t;j++){
            cin>>g[j];
            st[g[j]]=true;
        }
        for(int j=g[1];j<=g[t];j++)
            if(!st[j])
                for(int k=1;k<=t;k++)
                    if(!isIn[j][g[k]]){
                        isIn[j][g[k]]=true;                    
                        d[g[k]]++;
                    }
    }
    cout<<topsort();
    return 0;
}

请问前面10pts的代码怎么改呢?


|