[洛谷 1983][NOIP2013普及组]车站分级

题目链接

https://www.luogu.org/problem/P1983

题解

根据题意可以得出：一趟车停靠的所有车站的级别一定大于这趟车经过但不停靠的车站的级别。

于是我们可以建一张图，根据上文的方法，从低等级车站向高等级车站连一条边。因为题目保证有合法解，这张图一定是一张DAG，跑一遍拓扑排序即可得到各个车站的等级。

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct edge
{
 int v,next;
}e[1000005];
int vis[1005],path[1005],head[1005],f[1005][1005],t[1005],cnt;
queue<int> q;
void addedge(int u,int v)
{
 e[++cnt].v=v;
 e[cnt].next=head[u];
 head[u]=cnt;
}
int main()
{
 int n,m,ans=1;
 scanf("%d%d",&n,&m);
 for(int i=1;i<=m;i++)
 {
  int num;
  scanf("%d",&num);
  memset(vis,0,sizeof(vis));
  for(int j=1;j<=num;j++)
  {
   scanf("%d",&path[j]);
   vis[path[j]]=1;
  }
  for(int j=path[1];j<=path[num];j++)
   if(!vis[j])
   {
    for(int k=1;k<=num;k++)
     if(!f[j][path[k]])
     {
      addedge(j,path[k]);
      f[j][path[k]]=1;
      t[path[k]]++;
     }
   }
 }
 for(int i=1;i<=n;i++)
  if(!t[i])q.push(i),t[i]=-1;
 while(1)
 {
  while(!q.empty())
  {
   int u=q.front();
   q.pop();
   for(int i=head[u];i;i=e[i].next)
    if(f[u][e[i].v])t[e[i].v]--,f[u][e[i].v]=0;
  }
  for(int i=1;i<=n;i++)
   if(!t[i])q.push(i),t[i]=-1;
  if(q.empty())
  {
   printf("%d\n",ans);
   return 0;
  }
  else ans++;
 }
}