【基础练习】【拓扑排序】codevs3294 车站分级题解

蔚落 2022-08-05 02:44 161阅读 0赞

题目来源：NOIP2013 普及第四题

题目描述 Description

一条单向的铁路线上，依次有编号为1, 2, …, n的n个火车站。每个火车站都有一个级别，最低为1级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站x，则始发站、终点站之间所有级别大于等于火车站x的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点）  
例如，下表是5趟车次的运行情况。其中，前4趟车次均满足要求，而第5趟车次由于停靠了3号火车站（2级）却未停靠途经的6号火车站（亦为2级）而不满足要求。

![SouthEast][]

现有m趟车次的运行情况（全部满足要求），试推算这n个火车站至少分为几个不同的级别。

输入描述 Input Description

第一行包含2个正整数n, m，用一个空格隔开。  
第i+1行（1≤i≤m）中，首先是一个正整数s\_i（2≤s\_i≤n），表示第i趟车次有s\_i个停靠站；接下来有s\_i个正整数，表示所有停靠站的编号，从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。

输出描述 Output Description

输出只有一行，包含一个正整数，即n个火车站最少划分的级别数。

样例输入 Sample Input

\[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 Output

\[Sample 1\]  
2  
\[Sample 2\]  
3

数据范围及提示 Data Size & Hint

对于20%的数据，1 ≤ n, m ≤ 10；  
对于50%的数据，1 ≤ n, m ≤ 100；  
对于100%的数据，1 ≤ n, m ≤ 1000。

这道题目李晨说一看就是拓扑 我看了半天没看出来看了别人说才想明白⊙﹏⊙b汗 惭愧啊

基本思路是 对于每条线路 他中间的点 没有经过的级别一定严格小于经过的级别 因此每个没有经过的点指向每个经过的点连接一条边 这样构建一张图 比较稠密 在拓扑排序即可 拓扑排序出来几层就分几级

写的代码参考了黄学长的 因此基本一样 但第一次尝试全WA 因为ans=0放错了位置 修改后WA了一半 其实原因在这里（错误的代码）：

while (1)
    	{
    		int top=0;
    		for (int i=1;i<=n;i++)
    		{
    			if (!r[i])
    			{
    				r[i]=-1;
    				top++;
    				for (int j=1;j<=n;j++) 
    				  if (e[i][j])
    				  {
    				  	e[i][j]=0;
    				  	r[j]--;//maybe it is 0 now! 这里有可能产生了新的入度为0的点，而这个点本应该是下一层排序出来的
    				  }
    			}
    		}
    		if (!top) break;
    		ans++;

也就是说 不能找到一个点处理一个 应该存起来集中处理

那么放代码

//codevs3294³µÕ¾·Ö¼¶ NOIP2013ÆÕ¼°µÚËÄÌâ ¼´Ê¹ÊÇ×îºóÁËÒ²ÒªÕõÔú×ÅÐ´Ò»µã
    //copyright by ametake
    //Ð´²»ÍêÍíÉÏ»Ø¼ÒÐ´ ½ñÌìÐ´Íê
    #include
       
        
    #include
        
         
    using namespace std;
    
    int n,m,ans;
    const int maxn=0x3f3f3f3f;
    int r[1001]/*rudu*/,b[1001]/*every time clear,stop station*/,qu[1001];
    bool a[1001],e[1001][1001],inq[1001];
    
    int main()
    {
    	freopen("1.txt","r",stdin);
    	int si;
    	scanf("%d%d",&n,&m);//n point and m xianlu
    	memset(e,0,sizeof(e));
    	memset(r,0,sizeof(r));
    	for (int i=1;i<=m;i++)
    	{
    		scanf("%d",&si);
    		memset(a,0,sizeof(a));
    		for (int j=1;j<=si;j++)
    		{
    			scanf("%d",&b[j]);
    			a[b[j]]=1;
    		}
    		for (int j=b[1];j

`————————————————无责任分割线———————————————— 因为是准备NOIP，图论的专题基本就到此为止了，当然之后也会穿插一些练习。 Tarjan缩点没学会，李晨说不要学了，于是暂时放下。LCA可能还是要看一下，有时间还要尝试线段树平衡树（斜角四十五度仰望天空……） 下一个模块开数学吧 欧拉函数 逆元 组合数 这些都要学的 不知不觉博客的诗句积累了好多···整理了一下真是惊人啊 六一快乐虽然已经过去了 高考加油 准备搬楼 文化课也要加油 努力考清华【= = ——已而得舟，避诸洲，出北海，然后渡扬子江，入苏州洋，辗转四明、天台，以至于永嘉。`

[SouthEast]: /images/20220805/ecfaaa0762ce43c285cfd14896dfdd00.png