为什么输出如此奇怪??

P1983 [NOIP2013 普及组] 车站分级

薛定谔的狼 @ 2022-08-05 11:35:51

此题我的大体思路就是构建虚点建边+拓扑。 但是我觉得已经是没什么问题了,问题却依旧很大。 提交后只AC一个点,其他的要么输出1(即ans的初始值),要么是没有输出。 请求大佬出手相助,谢谢

#include<bits/stdc++.h>
using namespace std;
#define N 2500
#define M 1001000
int n,m,tot=0,ans=1,deg[N],f[N];
int head[N],ver[M],edge[M],nex[M];
void add(int u,int v,int w)//前向星加边 
{
    ver[++tot]=v;
    edge[tot]=w;
    nex[tot]=head[u];
    head[u]=tot;
}
void topsort()//拓扑板子 
{
    queue<int> q;
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
       if(!deg[i]) q.push(i),f[i]=1;
    while(q.size())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=nex[i])
        {
            int v=ver[i],w=edge[i];
            deg[v]--;
            if(!deg[v]) q.push(v);
            f[v]=max(f[v],f[u]+w);//记录车站等级 
            ans=max(ans,f[v]);//答案 
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int s,x,it;
        cin>>s>>x;//先单独输入起点 
        it=x;//用it表示一个指针,因为输入是有顺序的,所以每输入一个,就可以处理掉当前x与上一个x之间的点 
        add(n+i,x,1);//n+i是一个虚构的点,下同 
        deg[x]++;
        it++;
        for(int j=2;j<=s;j++)
        {
            cin>>x;
            while(it<x)//处理两个x之间的 
            {
                deg[n+i]++;
                add(it,n+i,0);
                it++;
            }
            add(n+i,x,1);//处理x 
            deg[x]++;
            it++;
        }
    }
    topsort();
    cout<<ans;
    return 0;
}

by fanchengqiao @ 2023-07-28 00:05:36

同问,大佬AC跟我说一声(✪ω✪)


|