Luogu P1983 车站分级

系统管理员 2023-06-02 13:59 7阅读 0赞

#include<cstdio>
    #include<queue>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    
    int n,m,s,stop[1005],head[1005],in[1005],dep[1005],ans,cnt;
    
    bool tag[1005],vis[1005][1005];
    
    struct edge{
        int v,next;
    }e[1000005];
    
    inline void add(int u,int v){
        e[++cnt].v=v;
        e[cnt].next=head[u];
        head[u]=cnt;
    }
    
    int main(){
        memset(head,-1,sizeof(head));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            memset(tag,0,sizeof(tag));
            scanf("%d",&s);
            for(int j=1;j<=s;j++){
                scanf("%d",&stop[j]);
                tag[stop[j]]=1;
            }
            for(int j=stop[1];j<=stop[s];j++){
                if(!tag[j]){
                    for(int k=1;k<=s;k++){
                        if(vis[j][stop[k]])continue;//防止建重边，因为e[1000005] 
                        add(j,stop[k]);
                        in[stop[k]]++;
                        vis[j][stop[k]]=1;
                    }
                }
            }
        }
        queue<int> q;
        for(int i=1;i<=n;i++){
            if(!in[i]){
                q.push(i);
                in[i]=-1;
                dep[i]=1;
            }
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=head[u];i!=-1;i=e[i].next){
                int v=e[i].v;
                in[v]--;
                if(!in[v]){
                    in[v]=-1;
                    q.push(v);
                    dep[v]=dep[u]+1;
                    ans=max(ans,dep[v]);
                }
            }
        }
        printf("%d\n",ans);
    }

转载于:https://www.cnblogs.com/Y15BeTa/p/11427709.html

发表评论取消回复

表情：

评论列表（有 0 条评论，7人围观）

还没有评论，来说两句吧...

相关阅读

相关 Luogu P1983 车站分级

include<cstdio> include<queue> include<iostream> include<algorithm>

系统管理员/ 2023年06月02日 13:59/ 0 赞/ 8 阅读

相关 LuoGu P1368 工艺

[LuoGu P1368 工艺][LuoGu P1368] 最小表示法的板子题.这个题可以用\\(n\\:log\_2\\:n\\)的\\(SA\\)求最小表示法也可以用更

雨点打透心脏的1/2处/ 2023年06月02日 11:59/ 0 赞/ 35 阅读

相关 P1983-车站分级

1 include <bits/stdc++.h> 2 using namespace std; 3 define pb push_back

Myth丶恋晨/ 2023年06月01日 08:55/ 0 赞/ 16 阅读

相关 java 车站分级_【图论经典题】NOIP2013 普及组 T4 车站分级（两种方法）

Solution 主要是按车站分级(就是按照题目意思来)和按车分级两种方法。方法一：按车站分级，我们知道一辆车经过的车站的等级一定大于没经过的车站的等级，这样就可以根据大

╰半夏微凉°/ 2022年11月05日 03:26/ 0 赞/ 22 阅读

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

题目来源：NOIP2013 普及第四题题目描述 Description 一条单向的铁路线上，依次有编号为1, 2, …, n的n个火车站。每个火车站都

蔚落/ 2022年08月05日 02:44/ 0 赞/ 181 阅读

相关 Luogu P3254 圆桌问题

[题目链接 \\(Click\\) \\(Here\\)][_Click_ _Here] 水题。记得记一下边的流量有没有跑完。 include <bits/st

傷城~/ 2022年01月09日 10:49/ 0 赞/ 184 阅读

相关 luogu P4116 Qtree3

题目描述给出N个点的一棵树（N-1条边），节点有白有黑，初始全为白有两种操作： 0 i : 改变某点的颜色（原来是黑的变白，原来是白的变黑） 1

﹏ヽ暗。殇╰゛Y/ 2021年12月24日 16:34/ 0 赞/ 222 阅读

相关 luogu P3146 （区间dp）

[传送门][Link 1] 题意：有一行格子，每个格子都有一个数值，如果相邻两个格子相同的话，可以合并成一个新的格子，新的格子的值为原来的值+1。现在问你通过不断的合

叁歲伎倆/ 2021年11月01日 09:10/ 0 赞/ 536 阅读

相关 [Luogu P1542] 包裹快递

[原题链接qwq][qwq] \\(Structure\\) 本题要求我们求出 `车的最大速度最小值` 。像求 `最大值最小`、`最小值最大` 这种类型的题目，我们

刺骨的言语ヽ痛彻心扉/ 2021年10月25日 11:57/ 0 赞/ 330 阅读

相关 LuoGu P1006 传纸条

[题目传送门][Link 1] 这题嘛...方格取数和这题一样一样的只不过这题是从左上到右下再回去罢了（来回一趟和来两趟有区别么？没有，那么这题和上题用一样的转移和状态就

你的名字/ 2021年10月01日 03:50/ 0 赞/ 276 阅读