wx6110fa547fd20 2021-08-10 07:37:50 阅读数:832
传送门
思路 :将每个车次车站的关系抽象化为边的关系,不停靠的车站等级肯定比停靠的车站等级低,因此可以建立一条边,然后就用拓扑排序搞搞就行了,注意判断重边。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e3+5; #define mst(a) memset(a,0,sizeof a) int n,m,in[N],vis[N],a[N]; bool edge[N][N]; vector<int>e[N]; int toposort(){ queue<pair<int,int> >q; int ans=1; for(int i=1;i<=n;i++) if(!in[i]) q.push({i,1}); while(q.size()){ int u=q.front().first; int g=q.front().second; q.pop(); for(auto v:e[u]){ in[v]--; if(!in[v]) q.push({v,g+1}),ans=max(ans,g+1);//找到最大等级. } } return ans; } int main(){ scanf("%d%d",&n,&m); for(int i=1,cnt;i<=m;i++){ scanf("%d",&cnt); mst(vis); for(int j=1;j<=cnt;j++) scanf("%d",&a[j]),vis[a[j]]=1; for(int j=a[1];j<=a[cnt];j++) if(!vis[j]) for(int k=1;k<=cnt;k++) if(!edge[j][a[k]]) edge[j][a[k]]=1,e[j].push_back(a[k]),in[a[k]]++; } printf("%d\n",toposort()); return 0; }
版权声明:本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢。 https://blog.51cto.com/u_15326986/3328266
《 老大哥要变小鲜肉 试驾北京EU5 PLUS
P1983 station classification (topological sorting) 》