P1983 [NOIP 2013 普及組] 車站分級 題解

題目鏈接

我的博客

前言

你知道你入度為 \(0\) 嗎？
因為你要入隊了。

思路

這道題要求至少分為幾個不同的級別，那么首先想到的就是拓撲排序。

如何建圖呢？

我們知道，每趟列車運行情況中，所有沒有停靠的站點級別必定比已經?？康恼军c級別小。是不是有思路了？我們只需要讓級別小的站點指向級別大的站點，然后跑拓撲排序即可。

具體的，讓每次沒有?？康恼军c指向?？康恼军c。下圖為樣例 \(1\) 的圖（沒有 \(7,8,9\) 三個點）

最后只需要看級別最高的是多少即可。

代碼

#include<cstdio>
#include<iostream>

#include<algorithm>
#include<queue>
using namespace std;
#define int long long 
#define ___ __int128
#define INF 0x3f3f3f3f3f3f3f3f 
inline int Read(){
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    return x*f;
}
inline void Write(int x){
	if(x<0) {putchar('-');x=-x;}
	if(x>9) Write(x/10);
	putchar(x%10+'0');
}
const int N=1e3+10,M=5e5+10;
int n,m,a[N],d[N],rk[N],ans;
//d[i]：i 結點入度
//rk[i]：i 車站級別
bool g[N][N],vis[N];
//g[i][j]：i 和 j 之間有沒有連邊，去重用的
struct node{
	int nxt,to;
}e[M];//邊的數組一定不要開小
int head[N],num_Edge=0;
void add_Edge(int from,int to){
	e[++num_Edge].nxt=head[from];
	e[num_Edge].to=to;
	head[from]=num_Edge;
}
queue<int> q;
signed main(){
	n=Read();m=Read();
	while(m--){
		for(int i=1;i<=n;i++) vis[i]=0;//vis[i]：本次是否停靠
		int k=Read();
		for(int i=1;i<=k;i++){
			int x=Read();
			vis[x]=1;
			a[i]=x;
		}
		for(int i=a[1];i<=a[k];i++){
			if(!vis[i]){
				for(int j=1;j<=k;j++){
					if(g[i][a[j]]) continue;
					add_Edge(i,a[j]); 
					d[a[j]]++;
					g[i][a[j]]=1;
				}
			}
		}
	}
    //拓撲排序板子
	for(int i=1;i<=n;i++){
		if(!d[i]) {
			q.push(i); 
			rk[i]=1;
		}
	}
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			rk[v]=max(rk[v],rk[u]+1);
			d[v]--;
			if(!d[v]) q.push(v); 
		}
	}
	for(int i=1;i<=n;i++){
		ans=max(ans,rk[i]);
	}
	printf("%lld\n",ans);
	return 0; 
}