4个点MLE呜呜呜呜呜求dalao调调

P1983 [NOIP2013 普及组] 车站分级

blackrockshtooer @ 2024-02-04 11:03:16

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {         //车站分级  拓扑排序

//    static class Edge{
//        int v,next;
//    }
    static int[][] edges = new int[2][1005*1000];        //edges[0] = next  edges[1] = v
    static int[] head = new int[1005];
//    static Edge[] edges = new Edge[1005*1005];
    static int[] level = new int[1005];
    static int[] flag = new int[1005];
    static int n,m,cnt=0;
    static int start,end;
    static int[] ind = new int[1005];
    static boolean[][] vis = new boolean[1005][1005];
    static void add(int u,int v){
        edges[1][cnt] = v;
        edges[0][cnt] = head[u];
        head[u] = cnt++;
    }
    static void kahn(){
        Queue<Integer> q = new LinkedList<>();
        for (int i=1;i<=n;i++){
            if (ind[i]==0){
                q.add(i);
                level[i] = 1;
            }
        }
        int u,v;
        while(!q.isEmpty()){
            u = q.poll();
            for (int i=head[u];i!=-1;i=edges[0][i]){
                v = edges[1][i];
                ind[v]--;
                level[v] = Math.max(level[u]+1,level[v]);
                if (ind[v]==0){
                    q.add(v);
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        int times;
        Arrays.fill(head,-1);
        for (int i=1;i<=m;i++){
            Arrays.fill(flag,0);
            times = sc.nextInt();
            for (int j=1;j<=times;j++){
                int cur = sc.nextInt();
                if (j==1){
                    start=cur;
                }
                if (j==times){
                    end=cur;
                }
                flag[cur]=1;
            }
            for (int j=start;j<=end;j++){
                if (flag[j]==1){
                    for (int k=start;k<=end;k++){
                        if (flag[k]==0&&vis[j][k]){
                            add(j,k);
                            vis[j][k]=true;
                            ind[k]++;
                        }
                    }
                }
            }
        }
        kahn();
        System.out.println(Arrays.stream(level).max().getAsInt());
    }
}

by tjx123456 @ 2024-02-04 11:09:46

阿巴,阿巴


by blackrockshtooer @ 2024-02-04 15:18:32

@tjx123456 佬


by CppHZ @ 2024-10-01 22:51:25

e.........要不你看下题解?题解传送门


|