P1983 [NOIP2013 普及组] 车站分级 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
由于Java速度的局限性,即使我写了基础的快读快输,仍然在第8个样例点处tle
大家可以自行去洛谷下载来验证
思路是这样的,我们把所有列车为停靠的车站指向已经停靠的车站,在这里,我们要记住去重,然后我们记录这些车站的先后关系。设置分级数组,默认每个车站的等级是一级,然后我们开始拓扑排序,a号车站链接的b号车站的等级等于b号的等级和a号车站的等级加1做对比取最大。
为什么呢,原因很简单,要最小的分级数量,那么我们就加一即可。
代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.math.MathContext;
import java.security.PublicKey;
import java.sql.SQLIntegrityConstraintViolationException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;
import javax.sound.midi.Soundbank;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
Scanner sc=new Scanner(System.in);
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw1=new PrintWriter(System.out);
String[] aStrings=br.readLine().split(" ");
aa=Integer.parseInt(aStrings[0]);
bb=Integer.parseInt(aStrings[1]);
al1=new ArrayList[aa+1];
visited=new int[aa+1];
rudu=new int[aa+1];
answer=new int[aa+1];
cc=new int[aa+1][aa+1];
int a,b,c,d,e,f,g;
for(a=1;a<=aa;a++) {
al1[a]=new ArrayList<>();
}
for(a=0;a<bb;a++) {//这就是用来存储边的过程
String[] bStrings=br.readLine().split(" ");
b=Integer.parseInt(bStrings[0]);
c=bStrings.length;
Arrays.fill(visited, 0);
for(d=1;d<c;d++) {
e=Integer.parseInt(bStrings[d]);
visited[e]=1;
}
f=Integer.parseInt(bStrings[1]);
g=Integer.parseInt(bStrings[c-1]);
for(int a1=f;a1<=g;a1++) {
if(visited[a1]==0) {
for(int b1=1;b1<c;b1++) {
int c1=Integer.parseInt(bStrings[b1]);
if(cc[a1][c1]==0) {
cc[a1][c1]=1;
al1[a1].add(c1);
rudu[c1]++;
}
}
}
}
}
tuopu();
int answer3=0;
for(int c22=1;c22<=aa;c22++) {
answer3=Math.max(answer3, answer[c22]);
}
System.out.println(answer3);
}
public static int aa,bb; //记录车站的数量和几条路线
public static ArrayList<Integer>[] al1;//存储边
public static LinkedList<Integer> ll1=new LinkedList<>();//存储入度为0的点
public static int[] rudu;//入度数组
public static int[] answer;//每个点的等级数组
public static int[][] cc;//判断是否已经存入a到b的一条边,这个数组是为了我们来去重边时所用
public static int[] visited;//判断一条路线中已经被经过的车站的编号
public static void tuopu() {
int a;
Arrays.fill(answer, 1);//初始把每个车站的等级设为1级。
for(a=1;a<=aa;a++) {
if(rudu[a]==0) {
ll1.add(a);
}
}
while(ll1.size()!=0) {//取出入度为0的点
int d=ll1.remove();
for(int c:al1[d]) {
rudu[c]--;
answer[c]=Math.max(answer[c], answer[d]+1);//不断更新等级
if(rudu[c]==0) {//入度为0了,那么就继续汪队列里面添加
ll1.add(c);
}
}
}
}
}