首页 > 代码库 > 2013车站分级
2013车站分级
一条单向的铁路线上，依次有编号为1, 2, …, n的n个火车站。每个火车站都有一个级别，最低为1级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站x，则始发站、终点站之间所有级别大于等于火车站x的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点）
例如，下表是5趟车次的运行情况。其中，前4趟车次均满足要求，而第5趟车次由于停靠了3号火车站（2级）却未停靠途经的6号火车站（亦为2级）而不满足要求。
现有m趟车次的运行情况（全部满足要求），试推算这n个火车站至少分为几个不同的级别。
第一行包含2个正整数n, m，用一个空格隔开。
第i+1行（1≤i≤m）中，首先是一个正整数s_i（2≤s_i≤n），表示第i趟车次有s_i个停靠站；接下来有s_i个正整数，表示所有停靠站的编号，从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。
输出只有一行，包含一个正整数，即n个火车站最少划分的级别数。
[Sample 1]
9 2
4 1 3 5 6
3 3 5 6
[Sample 2]
9 3
4 1 3 5 6
3 3 5 6
3 1 5 9
[Sample 1]
2
[Sample 2]
3
对于20%的数据，1 ≤ n, m ≤ 10；
对于50%的数据，1 ≤ n, m ≤ 100；
对于100%的数据，1 ≤ n, m ≤ 1000。
题解：
拓扑排序。
知道是拓扑找最长路了，既然要拓扑，图在哪里？！方法：要以所有没有到的车站为起点和所有到了的车站为终点连边。（注意：重边的处理，否则会超时的）。
var k,n,i,m,j,ii,ans:longint;
f:array[0..1001,0..1001]of boolean;
vis:array[0..1001]of boolean;
zhan,a:array[0..1001]of longint;
begin
readln(k,n);
for i:=1 to n do
begin
fillchar(vis,sizeof(vis),false);
read(m);
for j:=1 to m do read(a[j]);
for j:=1 to m-1 do
for ii:=a[j]+1 to a[j+1]-1 do vis[ii]:=true;
for j:=a[1] to a[m] do
if vis[j] then
for ii:=1 to m do f[a[ii],j]:=f[a[ii],j] or vis[j];
end;
fillchar(a,sizeof(a),0);
for i:=1 to k do
for j:=1 to k do a[j]:=a[j]+ord(f[i,j]);
n:=k;
while n>0 do
begin
zhan[0]:=0;
for i:=1 to k do
if a[i]=0 then
begin
inc(zhan[0]);
zhan[zhan[0]]:=i;
dec(a[i]);
end;
inc(ans);
n:=n-zhan[0];
for i:=1 to zhan[0] do
for j:=1 to k do a[j]:=a[j]-ord(f[zhan[i],j]);
end;
write(ans);
end.
2013车站分级