首页 > 代码库 > [NOIp2013普及组]车站分级

[NOIp2013普及组]车站分级

2024-11-21 10:08:02   202人阅读

思路：

对于每一趟车，将区间内所有经停的站和所有未经停的站连一条边，表示前者优先级一定高于后者，然后用Kahn跑一遍拓扑排序即可。然而这样会创造大量多余的边，会TLE1个点。
考虑一种优化：因为每趟车本身也有一个优先级，因此可以将这趟车也看作一个点，每次先所有将经停的站连一条边到这两车上，表示这些站的优先级一定大于等于车的优先级，再将车连若干边到未经停的点，表示车的优先级一定大于未经停的站的优先级。

 1 #include<queue> 2 #include<cstdio> 3 #include<cctype> 4 #include<cstring> 5 inline int getint() { 6     register char ch; 7     while(!isdigit(ch=getchar())); 8     register int x=ch^‘0‘; 9     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^‘0‘);10     return x;11 }12 const int N=2001,M=1000001;13 struct List {14     int to,next;15 };16 List e[M];17 int sz=0;18 int h[N]={0};19 int in[N]={0};20 inline void add_edge(const int u,const int v) {21     e[++sz]=(List){v,h[u]};22     h[u]=sz;23     in[v]++;24 }25 const int inf=0x7fffffff;26 int ans=0;27 int n,m;28 inline void kahn() {29     std::queue<std::pair<int,int> > q;30     for(register int i=1;i<=n;i++) {31         if(!in[i]) q.push(std::make_pair(i,1));32     }33     while(!q.empty()) {34         int x=q.front().first,d=q.front().second;35         q.pop();36         for(register int i=h[x];i;i=e[i].next) {37             if(!--in[e[i].to]) {38                 q.push(std::make_pair(e[i].to,d+1));39             }40         }41         ans=std::max(ans,d);42     }43 }44 int main() {45     n=getint(),m=getint();46     int b[n+1];47     for(register int i=1;i<=m;i++) {48         memset(b,0,sizeof b);49         int s=getint();50         int S=getint();51         b[S]=true;52         for(register int j=2;j<s;j++) {53             b[getint()]=true;54         }55         int T=getint();56         b[T]=true;57         for(register int j=S;j<=T;j++) {58             if(b[j]) {59                 add_edge(j,i+n);60             }61             else {62                 add_edge(i+n,j);63             }64         }65     }66     kahn();67     printf("%d\n",(ans+1)>>1);68     return 0;69 }

 

[NOIp2013普及组]车站分级


联系
我们