TLE90求解！

Code_lover @ 2024-06-02 19:57:14

#include<bits/stdc++.h>
using namespace std;
const int Max_S=1e3+10;
const int Size=1e5;
int N,M,Ans;
int S[Max_S],G[Size];
int A[Max_S][Max_S];
int l[Max_S][Max_S],Cnt[Max_S];
struct node{int u,v;};
inline int read(){
    int x=0,f=1;char st=getchar();
    while(st<'0'||st>'9'){if(st=='-') f=-1;st=getchar();}
    while(st>='0'&&st<='9') x=x*10+st-'0',st=getchar();
    return x*f;
}
void Bfs(int num){
    queue<node>q;
    q.push({num,1});
    while(!q.empty()){
        node tmp=q.front();
        q.pop();
        for(int i=1;i<=N;i++){
            if(l[i][tmp.u]==1&&tmp.v+1>G[i]){
                G[i]=tmp.v+1;
                q.push({i,tmp.v+1});
                Ans=max(Ans,G[i]);
            } 
        }
    }
}
int main(){
    N=read();M=read();
    for(int i=1;i<=M;i++){
        S[i]=read(); 
        queue<int>Lower;
        A[i][1]=read();
        for(int j=2;j<=S[i];j++){
            A[i][j]=read();
            for(int k=A[i][j-1]+1;k<A[i][j];k++) Lower.push(k);
        }
        while(!Lower.empty()){
            int j=Lower.front();Lower.pop();
            for(int k=1;k<=S[i];k++){
                if(l[A[i][k]][j]==0){l[A[i][k]][j]=1;Cnt[A[i][k]]++;}
            }
        }
    }
    for(int i=1;i<=N;i++){
        if(Cnt[i]==0){G[i]=1;Bfs(i);}
    }
    cout<<Ans<<endl;
    return 0;
}

by Phill @ 2024-06-15 17:39:19

@Code_lover

你超时的原因：

1. 你记录哪些站的时候用了queue，每push一次就是log级别的
2. 你判断两个点是否联通时遍历了全图
3. 多次搜索,每个点都会遍历多次

我多次尝试在你的算法不变的情况下优化，但都超时了，最终还是给你改成了拓扑排序qaq

（可能是我太菜了）

其实拓扑排序的思想跟你的这个搜索还是挺像的，跟你的搜索相比，就是先把入度为零的点全加到queue里，之后有入度为0的点，也加入queue里就行了

最后代码

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int Max_S=1e3+10;
const int Size=1e3 + 10;
int N,M,Ans;
int S,G[Size];
int A[Max_S];
int l[Max_S][Max_S],Cnt[Max_S];
struct node{int u,v;};

struct edge{
    int to, next;
}e[Size * 1000];
int cnt, head[Size];
inline void adde(int u, int v){
    cnt++;
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}

queue<int> q;
inline void Bfs(){
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        // for(int i=1;i<=N;i++){ // 这里遍历了全图，太慢
        //  if(l[i][tmp.u]==1&&tmp.v+1>G[i]){
        //      G[i]=tmp.v+1;
        //      q.push({i,tmp.v+1});
        //      Ans=max(Ans,G[i]);
        //  } 
        // }

        for(int i = head[tmp]; i; i = e[i].next){ //改成了链式前向星
            int v = e[i].to;
            G[v] = G[tmp] + 1;
            Ans = max(Ans, G[v]);
            Cnt[v]--;
            if(Cnt[v] == 0) q.push(v);

        }
    }
}
int stop[Size];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // N=read();M=read();
    cin >> N >> M;
    for(int i=1;i<=M;i++){
        for(int j = 0; j <= N + 1; ++j){
            stop[j] = 0;
        }
        // S=read(); 
        cin >> S;
        for(int j=1;j<=S;++j){
            // A[j]=read();
            cin >> A[j];
            // for(int k=A[i][j-1]+1;k<A[i][j];k++) Lower.push(k); //这里太慢
            stop[A[j]] = 1; 
        }
        // while(!Lower.empty()){
        //  int j=Lower.front();Lower.pop();
        for(int j = A[1]; j <= A[S]; ++j){
            if(stop[j]) continue;
            for(int k=1;k<=S;++k){
                if(l[A[k]][j]==0){
                    l[A[k]][j]=1;
                    adde(j, A[k]); 
                    ++Cnt[A[k]];
                }
            }
        }
    }
    for(int i=1;i<=N;++i){
        if(Cnt[i]==0){
            G[i]=1;
            // Bfs(i); 
            q.push(i);
        }
    }
    Bfs();
    cout<<Ans<<endl;
    return 0;
}

by Code_lover @ 2024-06-19 19:40:36

@Phill 三克油大佬