P1983 车站分级

P1983 车站分级

题解

 其实这道题可以跑一个拓扑排序

我们看这些这车站，沿途停过的车站一定比未停的车站级别高

所以我们想到：

未停靠的车站向已经停靠的车站连一条边，入度为0的车站级别就是1啦

然后我们把入度为0的边依次取出来，那么它的出边所指车站就一定比这个车站级别高

那么也就是说，一个车站的级别一定比所有指向它的车站中，级别最高的那个车站级别还要高1级

注意

a[ ]  暂时存储每一趟车站

flag[ ] 暂时判断每个车站停不停

vis[ ][ ] 防止建重边

 由于可能会建很多边，所以拓扑排序中与边有关的数组一定要开大

注意看这里

也就是说，不一定每个车站都要从头开到尾，起止点不一定

代码

#include<bits/stdc++.h>

using namespace std;

const int da=4000020;
const int maxn=10005;
int n,m,k;
int head[maxn],nxxt[da],in[maxn],to[da],cnt=0;
int ji[maxn],ans=0,a[maxn];
bool vis[maxn][maxn],flag[maxn];

void add(int start,int end)
{
    cnt++;
    to[cnt]=end;
    nxxt[cnt]=head[start];
    head[start]=cnt;
}

int main()
{
    scanf("%d%d",&n,&m);
    
    for(int i=1;i<=m;i++)
    {
        memset(flag,0,sizeof(flag));
        memset(a,0,sizeof(a));
        
        scanf("%d",&k);
        for(int j=1;j<=k;j++)
        {
            scanf("%d",&a[j]);
            flag[a[j]]=1;
        }
        for(int j=a[1];j<=a[k];j++)
        {
            if(!flag[j])
            {
                for(int y=1;y<=k;y++)
                {
                    if(!vis[j][a[y]])
                    {
                        add(j,a[y]);
                        in[a[y]]++;
                        vis[j][a[y]]=1;
                    }
                }
            }
            
        }
        
    }
    
    priority_queue<int,vector<int>,greater<int> >q;
    
    for(int i=1;i<=n;i++)
    {
        if(!in[i])
        {
            q.push(i);
            ji[i]=1;
        } 
        
    }
    
    while(!q.empty())
    {
        int now=q.top();
        q.pop();

        for(int e=head[now];e;e=nxxt[e])
        {
            ji[to[e]]=max(ji[to[e]],ji[now]+1);
            in[to[e]]--;
            if(!in[to[e]]) q.push(to[e]);
            ans=max(ans,ji[to[e]]);
        }
    }
    
    printf("%d
",ans);
    
    return 0;
}