Dreamlands @ 2022-10-18 21:02:17
RT,奇奇怪怪的错误
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,m,s[1010],t,rec_1,last,maxx,ans,rec2;
bool f[1010];
vector<int>dag[1010],ser2,G;
queue<int>ser1;
inline int read() {
int X=0;
bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-') {
f=1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9') {
X=(X<<1)+(X<<3)+ch-'0';
ch=getchar();
}
if(f==1) {
return ~(X-1);
} else {
return X;
}
}
int main() {
n=read(),m=read();
for(register int i=1; i<=m; i++) {
t=read();
last=read();
ser1.push(last);
for(register int j=2; j<=t; j++) {
rec_1=read();
ser1.push(rec_1);
for(register int k=last+1; k<rec_1; k++) {
ser2.push_back(k);
}
last=rec_1;
}
for(register int j=0; j<ser1.size(); j++) {
for(register int k=0; k<ser2.size(); k++) {
dag[ser1.front()].push_back(ser2[k]);
// printf("Line %d:%d->%d\n",j+1,ser1.front(),ser2[k]);
s[ser2[k]]++;
}
ser1.pop();
j--;
}
ser2.clear();
}
rec2=n+1;
for(register int i=1; i<=n; i++) {
if(s[i]==0) {
rec2--;
}
}
bool f114514=0,f2=0;
ser2.clear();
for(register int k=1; k<=n; k++) {
f114514=0,f2=0;
for(register int i=1; i<=n; i++) {
if(s[i]!=-1) {
f2=1;
}
if(s[i]==0) {
// printf("Line #:%d释放\n",i);
f114514=1;
// printf("Line *:%d\nLine !:",i);
for(register int j=0; j<dag[i].size(); j++) {
// s[dag[i][j]]--;
ser2.push_back(dag[i][j]);
// printf("[%d,%d] ",dag[i][j],s[dag[i][j]]);
}
// puts("");
dag[i].clear();
rec2--;
s[i]=-1;
}
}
for(register int i=0; i<ser2.size(); i++) {
s[ser2[i]]--;
}
ser2.clear();
if(f114514==1) {
ans++;
}
if(f2==0) {
break;
}
// printf("!!! %d %d %d\n",rec2,k,ans);
for(register int j=1; j<=n; j++) {
// printf("%d ",s[j]);
}
// puts("");
}
printf("%d",ans);
return 0;
}
by Dreamlands @ 2022-10-20 18:32:03
警示后人,不要用vector,因为倍增
by lalaouye @ 2022-10-27 21:12:43
可以用,需要判断重边
by lalaouye @ 2022-10-27 21:13:04
@Dreamlands
by Dreamlands @ 2022-10-30 08:58:42
@lalaouye123 细说
by lalaouye @ 2022-10-30 09:00:34
@Dreamlands 就是我在建边时判断了一下,如果两两之间已经有边了那就不用再建边了
by Dreamlands @ 2022-10-30 09:03:17
@lalaouye123 okkk,谢谢大佬
by cxlian25 @ 2023-01-06 14:43:42
@Dreamlands 什么意思啊,我也用邻接表mle了