建立虚拟中间节点求解

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

const int N=2005;
const int M=1000005;

int n, m;
int head[N], E=0;
queue<int> q;
int din[N];
int dist[N];
bool vis[N];
vector<int> ans;

struct Edge{int v, w, ne;}e[M];
void add(int a, int b, int c){
    e[E].v=b;
    e[E].ne=head[a];
    e[E].w=c;
    head[a]=E++;
    din[b]++;
}

void bfs(){
    for(int i=1; i<=n+m; ++i)
        if(!din[i]) q.push(i);
    while(!q.empty()){
        int node=q.front(); q.pop(); ans.push_back(node);
        for(int i=head[node]; ~i; i=e[i].ne){
            int v=e[i].v;
            int w=e[i].w;
            if(--din[v]==0) q.push(v);
        }
    }
}

int main(){
    cin>>n>>m;
    memset(head, -1, sizeof head);
    memset(vis, 0x00, sizeof vis);
    for(int i=1; i<=m; ++i){
        memset(vis, 0x00,sizeof vis);
        int cnt; // 第i趟车有cnt个停靠车站
        cin>>cnt;
        int start=n, end=1; // 记录起始站点和终止站点
        while(cnt--){
            int stop;
            cin>>stop;
            start=min(start, stop);
            end=max(end, stop);
            vis[stop]=true;
        }
        int ver=n+i; // 对于每趟车次设置一个虚拟中间节点
        for(int j=start; j<=end; ++j){
            if(!vis[j]) add(j, ver, 0); // 非停靠点连到虚拟节点
            else add(ver, j, 1); // 虚拟点连到停靠点
        }
    }
    bfs();
    for(int i=1; i<=n; ++i) dist[i]=1;
    for(int i=0; i<n+m; ++i){
        int u=ans[i];
        for(int j=head[u]; ~j; j=e[j].ne){
            int v=e[j].v;
            int w=e[j].w;
            dist[v]=max(dist[v], dist[u]+w);
        }
    }
    int res=0;
    for(int i=1; i<=n; ++i) res=max(res, dist[i]);
    cout<<res<<endl;
    return 0;
}