P1983 station classification (topological sorting)

wx6110fa547fd20 2021-08-10 07:39:18 阅读数:947

本文一共[544]字,预计阅读时长:1分钟~
p1983 station classification topological sorting
P1983 Station classification ( A topological sort )

  Portal

Ideas : Abstract the relationship of each train number and station into the relationship of edges , The level of non stopping station must be lower than that of stopping station , So you can create an edge , Then just do it with topological sorting , Pay attention to the judgment of heavy edges .

#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);// Maximum level found . 
}
}
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;
}

  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
版权声明:本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢。 https://car.inotgo.com/2021/08/20210810073742360f.html