车站分级——（拓扑排序+虚拟节点优化边的数量）

思路

如何实现

利用虚拟节点把m到n的多对多的映射变成两个一对多的映射m->1和1->n，使得边的数量从m*n优化到m+n,大大的降低了边的数量，降低了时间复杂度和空间复杂度。

C++ 代码

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=2010,M=1000010;
int h[N],e[M],ne[M],w[M],idx;
int r[N],dist[N],a[N];
int n,m,k,ans;
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void top_sort()
{
    queue <int> q;
    for(int i=1;i<=2*n;i++)
        if(r[i]==0)
            q.push(i);

    while(q.size())
    {
        int t=q.front();
        q.pop();

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            r[j]--,dist[j]=max(dist[j],dist[t]+w[i]);
            if(r[j]==0) q.push(j);
        }
    }
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++)
    {
        cin>>k;
        int left=1e9,right=0;
        for(int j=0;j<k;j++)
        {
            int x;
            cin>>x;
            a[x]=1;
            left=min(left,x),right=max(right,x);
        }

        for(int j=left;j<=right;j++)
        {   //虚拟节点的入边权值为1，出边权值为0
            if(a[j]) add(i+n,j,0),r[j]++;//i+n为虚拟节点，为了减少建边数量
            else add(j,i+n,1),r[i+n]++;//没有停下的站连向虚拟节点
            a[j]=0;
        }
    }

    top_sort();
    for(int i=1;i<=2*n;i++) ans=max(ans,dist[i]);
    cout<<ans+1<<endl;
    return 0;
}