50pts求助
查看原帖
50pts求助
138106
tgs9311楼主2021/8/15 22:08

大概是tarjan后面的处理出了问题?但是不知道为什么50pts了

#include<bits/stdc++.h>
using namespace std;
namespace FAST_IO
{
	template<typename T> void read(T &a)
	{
		a=0;
		int f=1;
		char c=getchar();
		while(!isdigit(c))
		{
			if(c=='-')
			{
				f=-1;
			}
			c=getchar();
		}
		while(isdigit(c))
		{
			a=a*10+c-'0';
			c=getchar();
		}
		a=a*f;
	}
	template <typename T> void write(T a)
	{
		if(a<0)
		{
			a=-a;
			putchar('-');
		}
		if(a>9)
		{
			write(a/10);
		}
		putchar(a%10+'0');
	}
	template <typename T> void writeln(T a)
	{
		write(a);
		puts("");
	}
}
const int maxn=1e4+10;
vector<int> g[maxn];
vector<int> g2[maxn];
int dfn[maxn],low[maxn],tot,n,m,vis[maxn];
int a[maxn],a2[maxn],ytn[maxn],zz,in[maxn];
stack<int> s;
void tarjan(int x)
{
	tot++;
	low[x]=dfn[x]=tot;
	s.push(x);
	vis[x]=true;
	for(int i=0;i<g[x].size();i++)
	{
		int to=g[x][i];
		if(!dfn[to])
		{
			tarjan(to);
			low[x]=min(low[x],low[to]);
		}
		else if(vis[to])
		{
			low[x]=min(low[x],dfn[to]);
		}
	}
	if(low[x]==dfn[x])
	{
		int tmp=0;
		zz++;
		while(1)
		{
			int now=s.top();
			s.pop();
			vis[now]=false;
			tmp+=a[now];	
			ytn[now]=zz;
			if(now==x)
			{
				break;
			} 
		}
		a2[zz]=tmp;
	}
}
int rans=0,tmp;
void dfs2(int now)
{
	tmp+=a2[now];
	for(int i=0;i<g2[now].size();i++)
	{
		int to=g2[now][i];
		dfs2(to);
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=m;i++)
	{
		int from,to;
		cin>>from>>to;
		g[from].push_back(to);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
		{
			tarjan(i);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<g[i].size();i++)
		{
			if(ytn[i]!=ytn[g[i][j]])
			{
				g2[ytn[i]].push_back(ytn[g[i][j]]);
				in[ytn[g[i][j]]]++;
			}
		}
	}
	for(int i=1;i<=zz;i++)
	{
		if(!in[i])
		{
			tmp=0;
			dfs2(i);
			rans=max(rans,tmp);			
		}
	}
	cout<<rans;
}

2021/8/15 22:08
加载中...