tarjan40分RE求调!
查看原帖
tarjan40分RE求调!
654763
smallpeople楼主2024/2/29 21:19

刚学tarjan的蒟蒻求调!

#include<bits/stdc++.h>
using namespace std;
const int N = 10005;

int n,m,val[N],tpx[N],ans;
int t,top,sum,vis[N],dfn[N],low[N],col[N];
int value[N],rd[N],res;
int f[N];
vector <int> p[N],pp[N],fpp[N];
queue <int> q;
int stac[N];

void tarjan(int u)
{
	dfn[u] = ++t;
	low[u] = t;
	stac[++top] = u;
	vis[u] = 1;
	
	for(int i = 0;i < p[u].size();i ++)
	{
		int v = p[u][i];
		if(!dfn[v])
		{
			tarjan(v);
			low[u] = min(low[u],low[v]);
		}
		else
		{
			if(vis[v])
				low[u] = min(low[u],low[v]);
		}
	}
	
	if(low[u] == dfn[u])
	{
		col[u] = ++sum;
		vis[u] = 0;
		while(stac[top] != u)
		{
			//col[stack[top]] = sum;
			value[sum] += val[stac[top]];
			col[stac[top]] = sum;
			top --;
		}
		value[sum] += val[stac[top]];
		top --;
	}
}

void topu()
{
	for(int i = 1;i <= sum;i ++)
		if(!rd[i])q.push(i);
	
	while(!q.empty())
	{
		int u = q.front();
		tpx[++res] = u;
		q.pop();
		for(int i = 0;i < pp[u].size();i ++)
		{
			int v = pp[u][i];
			rd[v] --;
			if(!rd[v])q.push(v);
		}
	}
}

int main()
{
	cin>>n>>m;
	for(int i = 1;i <= n;i ++)
		cin>>val[i];
	for(int i = 1;i <= m;i ++)
	{
		int a,b;
		cin>>a>>b;
		p[a].push_back(b);
	}
	
	for(int i = 1;i <= n;i ++)
		if(!dfn[i])tarjan(i);
	
	for(int u = 1;u <= n;u ++)
		for(int i = 0;i < p[u].size();i ++)
		{
			int v = p[u][i],uu = col[u],vv = col[v];
			if(uu != vv)
			{
				pp[uu].push_back(vv);
				fpp[vv].push_back(uu);//建反图,dp时可消除后效性。 
				rd[vv] ++;
			}
		}
	
	topu();
	
	for(int i = 1;i <= sum;i ++)
	{
		int v = tpx[i];
		f[v] = value[v];
		for(int j = 0;j < fpp[i].size();j ++)
			f[v] = max(f[v],f[fpp[v][j]] + value[v]);
	}
		
	for(int i = 1;i <= sum;i ++)
		ans = max(ans,f[i]);
	
	cout<<ans<<'\n';
	
	return 0;
}

除了AC的全部RE。求大佬帮调!

2024/2/29 21:19
加载中...