拓扑排序的SPFA,求助

P1983 [NOIP2013 普及组] 车站分级

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?


|