P1983 车站分级

传送门

先了解一下拓扑排序

那么了解了之后我们再来看一下这道题

看这个条件：

如果这趟车次停靠了火车站 x，则始发站、终点站之间所有级别大于等于火车站x 的都必须停靠。

这个条件等价于每一个没有停靠的点的级别都小于停靠过的站点的级别

题目要求的是最少划分的级别数

那么我们可以考虑拓扑排序

对于一条路径x1→x2，我们在这里面寻找没有停靠的站点，然后从这个没有停靠的站点向每一个停靠过的站点连边（注意开一个vis数组避免重边），然后拓扑排序板子稍微改一下就可以了

#include<bits/stdc++.h>
using namespace std;

const int MAXN=3000010;
const int maxn=1005;

int head[MAXN],to[MAXN],nxt[MAXN];
int in[maxn],cnt,dep[maxn];
int a[maxn],flag[maxn],vis[maxn][maxn],ans;
//flag标记是否停靠，vis去重边 

inline void add(int u,int v) 
{
    cnt++;
    to[cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}//邻接链表存边 

int n,m;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        memset(a,0,sizeof(a));
        memset(flag,0,sizeof(flag));
        int k;
        scanf("%d",&k);
        for(int j=1;j<=k;j++)
        {
            scanf("%d",&a[j]);
            flag[a[j]]=1;//标记 
        }
        for(int j=a[1]+1;j<=a[k];j++)
        {
            if(!flag[j])
            {
                for(int p=1;p<=k;p++)
                {
                    if(!vis[j][a[p]])
                    {
                        in[a[p]]++;
                        add(j,a[p]);
                        vis[j][a[p]]=1;
                    }
                }
            }
        }
        
    }
    
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        if(!in[i]) q.push(i),dep[i]=1;
        //刚开始入度就为0的点深度为1 
    }
    while(!q.empty())
    {
        int top=q.front();
        q.pop();
        for(int e=head[top];e;e=nxt[e])
        {
            int v=to[e];
            dep[v]=max(dep[v],dep[top]+1);
            //这个不加max也可以，因为下面的ans已经取过max了
            //不过加上也没问题 
            ans=max(ans,dep[v]);//更新答案 
            in[to[e]]--;//入度-- 
            if(!in[to[e]]) q.push(to[e]);
        }
    }
    cout<<ans;
    
}

P1983 车站分级

相关推荐