为什么输出如此奇怪??
查看原帖
为什么输出如此奇怪??
275982
薛定谔的狼楼主2022/8/5 11:35

此题我的大体思路就是构建虚点建边+拓扑。 但是我觉得已经是没什么问题了,问题却依旧很大。 提交后只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;
}
2022/8/5 11:35
加载中...