吸氧后TLE一个点,求救

P1983 [NOIP2013 普及组] 车站分级

fyss006 @ 2020-03-01 10:49:27

大佬们请救救菜鸡我 思路:级别高的站点指向低级站点后topo排序 感觉复杂度没有问题

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;
const int maxn=1005,maxm=1005*1005;
int head[maxn],nex[maxm],to[maxm],cnt=0;
int indegree[maxn],n,m;
bool link[maxn][maxn];
void add_edge(int u,int v){
    to[++cnt]=v;
    nex[cnt]=head[u];
    head[u]=cnt;
    indegree[v]++;
}
struct jx{
    int n,t;
};
queue<jx> q;
int topo(){
    int i,ans=0;
    for(i=1;i<=n;i++){
        if(!indegree[i]) q.push((jx){i,1});
    }
    while(!q.empty()){
        jx y=q.front();
        ans=max(ans,y.t);
        //cout<<"poping"<<y.n<<" "<<y.t<<endl;
        q.pop();
        for(i=head[y.n];i;i=nex[i]){
            int d=to[i];
            indegree[d]--;
            //cout<<d<<" "<<indegree[d]<<endl;
            if(!indegree[d]) q.push((jx){d,y.t+1});
        }
    }
    return ans;
}

int main(void){
    int i,j,k;
    std::ios::sync_with_stdio(false);
    cin>>n>>m;
    for(i=1;i<=m;i++){
        int t;
        bool f[maxn]={false};
        int fin=0,sta=0x7fffffff;
        cin>>t;
        for(j=1;j<=t;j++){
            int v;
            cin>>v;
            f[v]=1;
            fin=max(fin,v);
            sta=min(sta,v);
        }
        for(j=sta;j<=fin;j++){
            if(!f[j]) continue; 
            for(k=sta;k<=fin;k++){
                if(!f[k]&&!link[j][k]) add_edge(j,k),link[j][k]=1;
            }
        }
    }
    cout<<topo();
    return 0;
}

by Micro_Seven @ 2020-03-01 10:54:19

https://www.luogu.com.cn/paste/qlgb27ej


by 潜水的蒟蒻 @ 2020-03-01 11:01:56

@Micro_Seven 您都有这些了, 为什么不卡测评


by fyss006 @ 2020-03-01 11:02:27

@Micro_Seven 比赛吸不了臭氧啊233


by fyss006 @ 2020-03-01 11:03:53

求一个优化思路qwq


by Micro_Seven @ 2020-03-01 11:14:45

我是个蒟蒻,只是来凑热闹的


by _hqw_ @ 2020-03-13 19:25:02

@fyss006 考虑吸氧中毒 (逃


by djwj233 @ 2020-03-15 17:40:46

换个快读试试?


|