80分萌新求助,调了两天了qaq
查看原帖
80分萌新求助,调了两天了qaq
125429
SfumatoCannon_楼主2020/9/14 13:38

调了两天了,就是看不出来哪里有错误,在线求助(

不管我重构多少次代码,总是4,7两个点WA掉。。

另:我在tarjan函数后面发现有的点的"父亲"(即f数组)为0,所以在前面加了for循环。

我觉的我tarjan问题,但是又找不出来哪里有问题= =

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

int n,m1,m2,timea;
int p[10001],h1[10001],h2[10001],f[10001],dfn[10001],low[10001];
stack<int> st;
int vis[10001],dp[10001],rd[10001];

struct Edge
{
	int from,next,to;
};
Edge bian1[100001],bian2[100001];

void add1(int x,int y,int id)
{
	bian1[id].from=x;
	bian1[id].to=y;
	bian1[id].next=h1[x];
	h1[x]=id;
}

void add2(int x,int y)
{
	m2++;
	bian2[m2].from=x;
	bian2[m2].to=y;
	bian2[m2].next=h2[x];
	h2[x]=m2;
	rd[y]++;
}

void tarjan(int x)
{
	timea++;
	dfn[x]=low[x]=timea;
	st.push(x);
	int i,j;
	for (i=h1[x];i;i=bian1[i].next)
	{
		j=bian1[i].to;
		if (dfn[j]==0)
		{
			tarjan(j);
			low[x]=min(low[x],low[j]);
		}
		else
			low[x]=min(low[x],dfn[j]);
	}
	if (dfn[x]==low[x])
	{
		while (st.top()!=x)
		{
			p[x]+=p[st.top()];
			f[st.top()]=x;
			st.pop();
		}
		f[x]=x;
		st.pop();
	}
}

void lb()
{
	int i;
	for (i=1;i<=m1;i++)
	{
		if (f[bian1[i].from]!=f[bian1[i].to])
			add2(f[bian1[i].from],f[bian1[i].to]);
	}
}

int topo()
{
	queue<int> Q;
	int i;
	for (i=1;i<=n;i++)
		if (f[i]==i&&rd[i]==0)
		{
			Q.push(i);
			dp[i]=p[i];
		}
	while (!Q.empty())
	{
		int k=Q.front();
		Q.pop();
		for (i=h2[k];i;i=bian2[i].next)
		{
			dp[bian2[i].to]=max(dp[bian2[i].to],dp[k]+p[bian2[i].to]);
			rd[bian2[i].to]--;
			if (rd[bian2[i].to]==0)
				Q.push(bian2[i].to);
		}
	}
	int ans=0;
	for (i=1;i<=n;i++)
		ans=max(ans,dp[i]);
	return ans;
}

int main()
{
	cin>>n>>m1;
	int i,x,y;
	for (i=1;i<=n;i++)
		cin>>p[i];
	for (i=1;i<=m1;i++)
	{
		cin>>x>>y;
		add1(x,y,i);
	}
	for (i=1;i<=n;i++)
		f[i]=i;
	for (i=1;i<=n;i++)
		if (!dfn[i])
			tarjan(i);
	lb();
	cout<<topo();
	return 0;
}
2020/9/14 13:38
加载中...