zPatronus's blog

luoguP1983 车站分级

Posted on Edited on

题目

将每趟车看成一个虚点，每个站点看成实点

对于一辆车 虚点指向起点站到终点站所有经过的点 起点站到终点站所有没经过的点指向虚点

也就是

没经过（等级低）—>虚点—>经过（等级高）

这样做的好处是 可以避免O(mn^2)连边

其实这道题如果直接O(mn^2)，在经过和没经过的点上两两连边，也是可以过的。

这样拓扑跑一遍以后每个实点都有一个rank

任一拓扑序一定形如 实点-虚点-实点-虚点-实点….

假设拓扑起点的rank=0

实点 虚点 实点 虚点 … 实点
0 1 2 3 rk
1 2 rk/2+1

所以在实点的rk中取最大值，答案是rk/2+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
#define N 1100
#define max(a,b) ((a)>(b)?(a):(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define fsb(a,b,c) for(int a=b;a<=c;a++)
#define fbs(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
int n,m,s,x,into[N*2],vis[N],head[N*2],cnt=0,rk[N*2],ans=0;
int b[N*2],l,r,sz,start;
struct edge{
 int p,nt;
}a[N*N];
template<typename T>inline void rll(T &x){
 x=0;T f=1;char c=getchar();
 while(!isdigit(c))f=c=='-'?-1:f,c=getchar();
 while(isdigit(c))x=x*10+c-'0',c=getchar();
 x*=f;
}
inline void add(int x,int y){
 a[++cnt].p=y;a[cnt].nt=head[x];head[x]=cnt;
}
inline void addb(int x,int y){
 rk[x]=y;b[++r]=x;sz++;
}
int main(){
 rll(n);rll(m);//n车站 m车
 mem(into,0);mem(head,255); 
 fsb(i,1,m){
  rll(s);mem(vis,0);
  fsb(j,1,s){
   rll(x);vis[x]=1;
   start=j==1?x:start;
   into[x]++;add(i+n,x);
  }
  fsb(j,start,x)
   if(!vis[j]){
    into[i+n]++;add(j,i+n);
   }
 }
 l=1;r=0;sz=0;mem(rk,255);
 fsb(i,1,n+m)
  if(into[i]==0)addb(i,0);
 while(sz>0){
  int u=b[l];l++;sz--;
//  printf("%10d %d\n",u,rk[u]);
  for(int t=head[u];t!=-1;t=a[t].nt){
   int v=a[t].p;
   into[v]--;rk[v]=max(rk[v],rk[u]+1);
   if(into[v]==0)addb(v,rk[v]);
  }
 }
 fsb(i,1,n)ans=max(ans,rk[i]);
 printf("%d\n",ans/2+1);
 return 0;
}