Mr_think @ 2021-02-02 08:52:52
虚点做法
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=1005;
int n,m,ans=0;
bool vis[N*N];
int du[N],f[N*N];
int hd[N*N],nt[N*N],e[N*N],cnt=0;
inline int maxx(int x,int y){return x>=y?x:y;}
inline void tian(int x,int y){
e[++cnt]=y,nt[cnt]=hd[x],hd[x]=cnt;
du[y]++;
}
inline void topo(){
queue<int> q;
int p=m+n;
for(int i=1;i<=p;i++){
if(!du[i]){
q.push(i);
if(i<=n) f[i]=1;
else f[i]=0;
}
}
while(q.size()){
int x=q.front(); q.pop();
for(int i=hd[x];i;i=nt[i]){
int y=e[i];
if(y<=n) f[y]=maxx(f[x]+1,f[y]);
else f[y]=maxx(f[x],f[y]);
ans=maxx(ans,f[y]);
if(--du[y]==0)
q.push(y);
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
memset(vis,0,sizeof(vis));
int s;scanf("%d",&s);
int tou,wei,xu=n+i;
for(int j=1;j<=s;j++){
int a;scanf("%d",&a);
if(j==1) tou=a;
if(j==s) wei=a;
vis[a]=1;
tian(xu,a);
}
for(int j=tou;j<=wei;j++)
if(!vis[j]) tian(j,xu);
}
topo();
printf("%d",ans);
return 0;
}
by iMya_nlgau @ 2021-02-02 09:34:11
@Mr_think 把你的 N 开到 2005 就过了 https://www.luogu.com.cn/record/45964774
大概是数组开小了 (
by Mr_think @ 2021-02-02 09:56:55
感谢