P1983 车站分级

题面:https://www.luogu.org/problem/P1983

首先我们来谈一谈邻接表+dfs: 假设有一辆车经过三个车站ai,aj,ak(ai,aj,ak车站编号递增) 那么在ai,aj之间的a(i+1),a(i+2),.......,a(j-1)的级别一定是严格小于ai和aj的级别的 同理,在aj,ak之间的a(j+1),a(j+2),.......,a(k-1)的级别也一定是严格小于aj,ai的级别的 那么我么可以得出,在ai,ak之间的a(i+1),a(i+2),......,a(j-1),a(j+1),........a(k-1)的级别一定是严格小于ai,aj和ak的级别的 如果你还没看明白,那么我们再反过来看, ai,aj和ak的级别一定是严格大于在ai,ak之间的a(i+1),a(i+2),......,a(j-1),a(j+1),........a(k-1)的级别的. 看到这个,我们是不是很容易就能够想到将整个行进路线转为一个有向图, 将所有小于ai,aj,ak级别的车站都和ai,aj,ak连接加一条边,再将所有入度为0的跑一边dfs即可 这里要注意了,光是dfs会超时,所以必须要用记忆化搜索来做Code: #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #include<ctime> using namespace std; const int N=1000005,M=1005;//注意这里需要将数组开到2*N,否则会爆,二维数组开到N即可 long long n,m,s,x[N],to,head[N],j,a,k,ans,dp[N],i; bool used[M][M]; struct node{long long u,v,next,id; }edge[N]; void push(long long u,long long v){to++;edge[to].next=head[u];edge[to].u=u;edge[to].v=v;head[u]=to;edge[v].id++;//统计入度used[u][v]=true;//因为这里会出现重边现象,所以每次做加边操作后要将这条边标记一下}//邻接表,就不需我多做叙述了吧 long long dfs(long long u){//记忆化搜索long long l;if(dp[u]!=-1){//记搜的标志return dp[u];}dp[u]=1;for(l=head[u];l!=-1;l=edge[l].next){//邻接表中的所有元素顺序枚举dp[u]=max(dp[u],dfs(edge[l].v)+1);//方程:f(i)=max{f(j)+1};}return dp[u]; } int main(){memset(head,-1,sizeof(head));scanf("%lld%lld",&n,&m);for(i=1;i<=m;i++){scanf("%lld",&s);for(j=1;j<=s;j++){scanf("%lld",&x[j]);}for(j=2;j<=s;j++){for(k=x[j-1]+1;k<x[j];k++){//枚举在x[j-1]和x[j]之间的所有小于x[j],x[j-1]级别的车站for(a=1;a<=s;a++){if(!used[x[a]][k]){//如果不是重边push(x[a],k);//当前枚举到的车站与所有车站加边}}}}}memset(dp,-1,sizeof(dp));//因为要取最大值,所以初始值全部为-1for(i=1;i<=n;i++){if(edge[i].id==0){//如果当前入度为0ans=max(ans,dfs(i));//每次跑一边dfs就行}}printf("%lld\n",ans);//输出ansreturn 0; }接着,我们再来看拓扑排序的做法 其实,拓扑排序本质上就是找到一个入度为0的点然后输出,接着从网中删除此顶点及所有出边,直到不存在入度为0的点结束, 那么,我们就可以直接统计一下到底进行了几次拓扑排序,也就是经几次以上操作后不存在入度为0的点了. 虽然拓扑排序算法复杂度高,不易理解,效率也不容乐观,但是我们还是要写一写滴.Code: #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #include<ctime> using namespace std; const int N=1000005,M=1005; long long n,m,s,x[N],to,head[N],j,a,k,ans,i,top,vis[N],q[N]; bool used[M][M]; struct node{long long u,v,next,id; }edge[N]; void push(long long u,long long v){to++;edge[to].next=head[u];edge[to].u=u;edge[to].v=v;head[u]=to;edge[v].id++;//统计入度used[u][v]=true;//因为这里会出现重边现象,所以每次做加边操作后要将这条边标记一下}//邻接表,就不需我多做叙述了吧int main(){freopen("level.in","r",stdin);freopen("level.out","w",stdout);memset(head,-1,sizeof(head));scanf("%lld%lld",&n,&m);for(i=1;i<=m;i++){scanf("%lld",&s);for(j=1;j<=s;j++){scanf("%lld",&x[j]);}for(j=2;j<=s;j++){for(k=x[j-1]+1;k<x[j];k++){//枚举在x[j-1]和x[j]之间的所有小于x[j],x[j-1]级别的车站for(a=1;a<=s;a++){if(!used[x[a]][k]){//如果不是重边push(x[a],k);//当前枚举到的车站与所有车站加边}}}}} //之前部分不变,判重边,加边,记录入度while(1){//拓扑排序top=0;for(i=1;i<=n;i++){if(!vis[i]&&!edge[i].id){//如果此点入度为0且没有被访问过q[++top]=i;//q是一个栈数组,记录此次找到的入度为0的点vis[i]=1;//标记为已经访问过了}}if(!top){//如果栈是空的,即没有找到入度为0的点,那么说明拓扑排序已经进行完毕,退出循环break;}for(k=1;k<=top;k++){//枚举栈里的所有元素for(i=1;i<=n;i++){if(used[q[k]][i]){//如果有这条边used[q[k]][i]=0;//把这条边删除edge[i].id--;//入度--}}}ans++;//操作次数++}printf("%lld\n",ans);//输出ansreturn 0; }

转载于:https://www.cnblogs.com/ukcxrtjr/p/11382412.html

总结

以上是生活随笔为你收集整理的P1983 车站分级的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。