juruo救助 T掉一个点

P1983 [NOIP2013 普及组] 车站分级

王奕霏 @ 2019-03-10 11:35:15

#include<iostream>
#include<vector>
#include<queue>

using namespace std;
int n, m, t[1010];
int level[1010], ru[1010];
bool edg[1010][1010];
struct Node{
    int from;
    int to;
};
vector<Node> edges[1010];
queue<int> q;

void bfs(){
    for(int i=1;i<=n;i++){
        if(ru[i]==0){
            q.push(i);
            level[i]=1;
        }
    }
    while(!q.empty()){
        int top=q.front(); q.pop();
        for(int i=0;i<edges[top].size();i++){
            int t=edges[top][i].to;
            ru[t]--;
            if(ru[t]==0){
                level[t]=level[top]+1;
                q.push(t);
            }
        }
    }
    return;
}

int main(){
    cin >> n >> m;
    for(int i=0;i<m;i++){
        memset(t, 0, sizeof(t));
        int s;
        cin >> s;
        int a, from=0x3f3f;
        for(int j=0;j<s;j++){
            cin >> a;
            if(a<from) from=a; 
            t[a]=true;
        }
        for(int j=from;j<=a;j++){
            if(!t[j]) continue;
            for(int k=from;k<=a;k++){
                if(t[k]) continue;
                if(edg[k][j]) continue;
                edg[k][j]=true;
                Node b;
                b.from=k;
                b.to=j;
                edges[b.from].push_back(b);
                ru[j]++;
            }
        }
    }
//  for(int i=1;i<=n;i++) cout << ru[i] << " ";
    bfs();
//  cout << endl;
//  for(int i=1;i<=n;i++) cout << level[i] << " ";
//  cout << endl;
//  for(int i=1;i<=n;i++){
//      cout << i << ": ";
//      for(int j=0;j<edges[i].size();j++){
//          cout << edges[i][j].to << " ";
//      }
//      cout << endl;
//  }
    int max=0;
    for(int i=1;i<=n;i++) if(level[i]>max) max=level[i];
    cout << max << endl;
    return 0;
}

求巨佬帮忙看看如何优化


by clockwhite @ 2019-03-10 11:36:53

当然是吸氧快读啦qwq


by 王奕霏 @ 2019-03-10 11:40:04

@clockwhite 强!!!! 可惜我不会写QAQ


by ycyaw @ 2019-03-10 11:40:55


by ycyaw @ 2019-03-10 11:42:10

不会写快读就吸个氧换scanf吧,我记得这题有点卡常的


by 王奕霏 @ 2019-03-10 11:48:04

@ιχγббб 写了,依然T一个点


by 王奕霏 @ 2019-03-10 11:48:37

看大家运行时间平均都是我的十分之一QAQ


by 王奕霏 @ 2019-03-10 11:49:50

他们都200ms左右,我的貌似1996ms QAQ


by ycyaw @ 2019-03-10 11:50:28

@王奕霏 我是吸氧过的 https://www.luogu.org/recordnew/show/16837669

https://www.luogu.org/recordnew/show/16837828


by 7KByte @ 2019-03-10 11:50:31

换掉STL


by DARKSTALKING @ 2019-03-10 11:51:35

用gets吧,也许能卡进


| 下一页