WsW_ @ 2023-08-15 10:14:30
过不了样例
#include<bits/stdc++.h>
using namespace std;
struct node{
int val,next,to;
}edg[1000005];
int elen;
queue<int> q;
int n,m,s;
int in[1003];
int last,a;
int fans;
int ans[1003];
bool vis[1005];
int head[1005];
int stop[1003];
bool istop[1003];
void add(int u,int v,int val){
elen++;
edg[elen].to=v;
edg[elen].val=val;
edg[elen].next=head[u];
head[u]=elen;
in[v]++;//这里修改了入度
}
void SPFA(int s){
ans[s]=max(ans[s],1);
q.push(ans[s]);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=edg[i].next){
int to=edg[i].to;
in[to]--;
int cost=edg[i].val;
if(ans[to]<ans[x]+cost){
ans[to]=ans[x]+cost;
fans=max(fans,ans[to]);
if(in[to]==0){
q.push(to);
}
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
for(int i=1;i<=n;i++)istop[i]=0;
scanf("%d",&s);
for(int i=1;i<=s;i++){
scanf("%d",&stop[i]);
istop[stop[i]]=1;
}
for(int j=stop[1];j<=stop[s];j++){
if(!istop[j]){
for(int k=1;k<=m;k++){
add(stop[k],j,1);
}
}
}
}
for(int i=1;i<=n;i++){
if(in[i]==0&&head[i]>0){
// cout<<i<<"\n";
SPFA(i);
}
}
printf("%d",fans);
return 0;
}
by zxjn @ 2023-09-25 22:08:48
什么是SPFA?