薛定谔的狼 @ 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跟我说一声(✪ω✪)