$\texttt{\textcolor{red}{WA}}$ 60 Pts 求助
查看原帖
$\texttt{\textcolor{red}{WA}}$ 60 Pts 求助
545986
Jerrycyx楼主2022/5/29 10:46

WA\texttt{\textcolor{red}{WA}} 了最后三个点,都是第一行出错,代码如下:

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>

#define N 100005
#define M 1000005

using namespace std;

int n,m;
int x;

struct Allan{
	int from,to;
	int next;
}edge[M];
int tot=0;
int head[N];
int from[N],to[N];

int dfn[N],low[N];
int sta[N],top;
int num=0;
int scc[N],cnt=0;
int sum[N];

int deg[N];
int f[N],s[N];
int topcnt=0;

bool flag[N];
int d[N],a[N];
int out[N];
int ans1,ans2;

inline void add(int from,int to)
{
	tot++;
	edge[tot].from=from;
	edge[tot].to=to;
	edge[tot].next=head[from];
	head[from]=tot;
	deg[to]++;
	out[from]++;
	return;
}

inline void Get()
{
	scanf("%d%d%d",&n,&m,&x);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&from[i],&to[i]);
		add(from[i],to[i]);
	}
	return;
}

void Tarjan(int x)
{
	low[x]=dfn[x]=++num;
	sta[++top]=x;
	for(int i=head[x];i;i=edge[i].next)
	{
		int to=edge[i].to;
		if(dfn[to]==0)
		{
			Tarjan(to);
			low[x]=min(low[x],low[to]);
		}
		else if(scc[to]==0)
			low[x]=min(low[x],dfn[to]);
	}
	if(dfn[x]==low[x])
	{
		cnt++;
		while(sta[top+1]!=x)
		{
			scc[sta[top]]=cnt;
			sum[cnt]++;
			top--;
		}
	}
	return;
}
inline void Tarjan_All()
{
	for(int i=1;i<=n;i++)
		if(dfn[i]==0) Tarjan(i);
	return;
}

inline bool cmp(Allan x,Allan y)
{
	if(x.from==y.from) return x.to<y.to;
	else return x.from<y.from;
}

void Rebuild()
{
	for(int i=1;i<=m;i++)
	{
		edge[i].from=scc[edge[i].from];
		edge[i].to=scc[edge[i].to];
	}
	sort(edge+1,edge+m+1,cmp);
	memset(head,0,sizeof(head));
	memset(deg,0,sizeof(deg));
	memset(out,0,sizeof(out));
	tot=0;
	for(int i=1;i<=m;i++)
	{
		if(edge[i].from!=edge[i].to&&(edge[i].from!=edge[i-1].from||edge[i].to!=edge[i-1].to))
		{
			add(edge[i].from,edge[i].to);
		}
	}
	m=tot;
	return;
}

void Topsort()
{
	queue<int> q;
	for(int i=1;i<=n;i++)
	{
		if(deg[i]==0)
		{
			f[i]=sum[i];
			s[i]=1;
			ans1=max(ans1,f[i]);
			q.push(i);
		}
	}
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=edge[i].next)
		{
			int y=edge[i].to;
			deg[y]--;
			if(deg[y]==0)
				q.push(y);
			if(f[x]+sum[y]>f[y])
			{
				f[y]=f[x]+sum[y];
				ans1=max(ans1,f[y]);
				s[y]=0;
			}
			if(f[x]+sum[y]==f[y])
				s[y]=(s[y]+s[x])%(::x);
		}
	}
	return;
}

inline void Print()
{
	for(int i=1;i<=n;i++)
		if(f[i]==ans1)
			ans2=(ans2+s[i])%x;
	printf("%d\n%d\n",ans1,ans2);
	return;
}

int main()
{
	Get();
	Tarjan_All();
	Rebuild();
	Topsort();
	Print();
	return 0;
}

::x 代表访问全局变量 x

2022/5/29 10:46
加载中...