MLE80啊啊啊啊，求巨佬调

P1983 [NOIP2013 普及组] 车站分级

Statax @ 2024-04-01 12:50:19

#include<bits/stdc++.h>
using namespace std;
const int N=1005;

int n,m;
int len;
int i,j,k;
int deg[N],stop[N];
bool will[N];
vector<int>G[N];

int toposort(){
    int ans=0;
    queue<pair<int,int>>q;
    for(int i=1;i<=n;i++)
        if(!deg[i])
            q.push({i,1});

    int x,now;  
    while(!q.empty()){
        x=q.front().first;
        now=q.front().second;
        ans=now;q.pop();

        for(auto y:G[x]){
            if(!--(deg[y])){
                q.push({y,now+1});
            }
        }
    }

    return ans;
}

int main(){
    cin>>n>>m;

    for(i=1;i<=m;i++){
        memset(will,0,sizeof(will));
        cin>>len>>stop[1];

        for(j=2;j<=len;j++){
            cin>>stop[j];
            for(k=stop[j-1]+1;k<stop[j];k++){
                will[k]=1;  
            }
        }   

        for(j=1;j<=len;j++){
            for(k=stop[1]+1;k<stop[len];k++){
                if(will[k]){
                    G[stop[j]].push_back(k);
                    deg[k]++;
                }
            }
        }
    }   

    cout<<toposort()<<endl;
    return 0;
}

by Tomzying @ 2024-04-02 13:06:52

改为邻接矩阵存图就行了，注意重边。

by fengzhaoyu @ 2024-05-18 16:36:20

@Stroap_QwQ

可以定义一个rec[i][j]表示i到j是否走过如过走过，就不管他。

int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        memset(vis,0,sizeof vis);
        int k;cin>>k;
        for(int j=1;j<=k;j++) cin>>a[j],vis[a[j]]=1;
        for(int j=a[1];j<=a[k];j++)
        {
            if(!vis[j])
            {
                for(int s=1;s<=k;s++)
                {
                    if(re[j][a[s]]) continue;
                    re[j][a[s]]=1;
                    g[j].push_back(a[s]);
                    in[a[s]]++;
                }
            }
        }
    }