王奕霏 @ 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吧,也许能卡进