tarjan+拓扑求调
查看原帖
tarjan+拓扑求调
1013142
Chizuru_Ichinose楼主2024/3/15 20:29

自己测试应该是拓扑排序有问题,但找不出哪里写错了,跪求调

#include<bits/stdc++.h>
using namespace std;
const int kMax=1e4+4;
const int maxn=1e5+6;
int dfn[kMax],low[kMax];
vector<int> edge[maxn];
vector<int> G[maxn];//新图
bool vis[kMax];
int n,m,top,tot;
int in[kMax],to[kMax];
int st[kMax];
int col[kMax],cnt;//新点的编号,数量
int ind[kMax];
int dis[kMax],w[kMax];
int f[kMax];
void tarjan(int index)
{
	vis[index]=1;
	dfn[index]=low[index]=tot++;
	st[++top]=index;
	for(int i=0;i<edge[index].size();i++)
	{
		int temp=edge[index][i];
		if(!dfn[temp])
		{
			tarjan(temp);
			low[index]=min(low[index],low[temp]);
		}
		else if(vis[temp])//in stack
		{
			low[index]=min(low[index],dfn[temp]);
		}
	}
	if(dfn[index]==low[index])
	{	
		cnt++;
		while(st[top+1]!=index)
		{	
			w[cnt]+=dis[st[top]];
			col[st[top]]=cnt;
			vis[st[top--]]=0;
		}

	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>dis[i];
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		in[i]=u;
		to[i]=v;
		edge[u].push_back(v);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i]) tarjan(i);
	}
	// for(int i=1;i<=cnt;i++) cout<<w[i]<<endl;
	for(int i=1;i<=m;i++)
	{
		if(col[in[i]]!=col[to[i]])
		{
			G[col[in[i]]].push_back(col[to[i]]);
			ind[col[to[i]]]++;
			// cout<<col[in[i]]<<" "<<col[to[i]]<<endl;
		}
	}
	queue<int> q;
	for(int i=1;i<=cnt;i++)
	{		
		if(!ind[i])
		{
			q.push(i);
			f[i]=w[i];
		}
	}
	int ans=0;
	while(!q.empty())
	{
		int inn=q.front();
		q.pop();
		for(int i=0;i<G[inn].size();i++)
		{
			int too=G[inn][i];
			ind[too]--;
			f[too]=max(f[inn]+w[inn],f[too]);
			if(!ind[too]) q.push(too);
		}
		ans=max(ans,f[inn]);
	}
	// for(int i=1;i<=cnt;i++)
	// {
		// ans=max(ans,f[i]);
	// }
	cout<<ans<<endl;
	return 0;
}
2024/3/15 20:29
加载中...