本文共 3138 字，大约阅读时间需要 10 分钟。

题目

fateice 来到了魔方俱乐部旅行。

魔方俱乐部有N个分部，每个分部均有且仅有一个虫洞，但是这虫洞只能通往一个分部。

每个分部有一个 orzFang 价值，第i个分部的 orzFang 价值为A[i]。

现在他想知道，从第i个分部出发，并只通过虫洞前往下一个分部，orzFang 价值之和最多是多少（到达一个分部多次只计算1次 orzFang 价值）。

输入格式

第一行为一个正整数N 。 第二行有N个非负整数A[i] ，表示了每个分部的 orzFang 价值。 第三行有N个正整数F[i] ，表示通过第i个分部的虫洞所到达的分部为F[i] ，可能出现F[i]=i的情况。 输出格式 包括N行，第i行包含一个非负整数，表示从第i个分部出发，orzFang 价值之和的最大值为多少。

样例

样例输入 8 5 4 3 2 1 1 1 1 2 3 1 1 2 7 6 8 样例输出 12 12 12 14 13 2 2 1 数据范围与提示 对于20%的数据，N≤10。 对于40%的数据，N≤1000。 对于100%的数据，1≤N≤2e5，1≤Ai≤10⁴

思路

首先看到这种带环的，而且i只会有一个F[i]，

蒟蒻就自然而然的想到了tarjan，对于这种环也就是强连通分量， 于是就往下写了缩点，最后用记忆化搜索去得到每一个i的ans

可就是莫名其妙就MLE，

90分代码（MLE）

如果有大佬知道蒟蒻MLE于何处，必当万分感谢！！！

#include 
   
    #include 
    
     using namespace std;#define MAXN 200001stack < int > q;int n, cnt;int orz[MAXN], f[MAXN];int scc[MAXN], ans[MAXN];bool in_queue[MAXN];void tarjan ( int u ) {
   	if ( scc[u] )		return;	if ( in_queue[u] ) {
   		cnt ++;		int head;		while ( ! q.empty() && q.top() != u ) {
   			head = q.top();			scc[head] = cnt;			ans[cnt] += orz[head];			q.pop();		}		head = q.top();		scc[head] = cnt;		ans[cnt] += orz[head];		q.pop();		while ( ! q.empty() )			q.pop();		return;	}	in_queue[u] = 1;	q.push ( u );	tarjan ( f[u] );	in_queue[u] = 0;}int dfs ( int u ) {
   	if ( ans[scc[u]] )		return ans[scc[u]];	return ans[scc[u]] = dfs ( f[u] ) + orz[u];}int main() {
   	scanf ( "%d", &n );	for ( int i = 1;i <= n;i ++ )		scanf ( "%d", &orz[i] );	for ( int i = 1;i <= n;i ++ )		scanf ( "%d", &f[i] );	for ( int i = 1;i <= n;i ++ ) {
   		if ( ! scc[i] ) 			tarjan ( i );		if ( ! scc[i] )			scc[i] = ++ cnt;	}	for ( int i = 1;i <= n;i ++ )		if ( f[i] == i )			printf ( "%d\n", orz[i] );		else			printf ( "%d\n", dfs ( i ) );	return 0;}
    
   

题解

AC思路就是，通过题意，很容易发现数据长得是格外好看

描述一下就是多个环，然后环上套了几条链 极端数据F[i]=i，就有可能是一条单链加一个自环，也不影响

对于这种一条条的单链，我们可以思考拓扑排序，甩到栈里面去

为什么是栈呢？ 因为栈是先进后出，后进先出，我们正好要得到后进的F[i]答案再去更新i的答案

然后，就只剩下一个又一个互不打扰的环了，

因为是环，所以从环上任意一个点都可以开始搜索更新答案 我们可以用队列来模拟，把这个环上的节点在dfs更新ans的时候 顺便记录一下经过哪些节点，最后把队列清空的时候就顺便更新一下ans[i]

环处理好了的话就回到了之前栈的处理上，从后往前扫栈，直接更新ans[i]就可以了

可以保证i能走到的虫洞都已经有了答案

代码实现

#include 
   
    #include 
    
     #include 
     
      using namespace std;#define MAXN 200005queue < int > q;stack < int > sta;int n;int d[MAXN], f[MAXN], orz[MAXN], ans[MAXN];bool vis[MAXN];void Top_sort () {
   	for ( int i = 1;i <= n;i ++ )		if ( ! d[i] )			q.push ( i );	while ( ! q.empty() ) {
   		int t = q.front();		q.pop();		sta.push( t );		d[f[t]] --;		if ( ! d[f[t]] )			q.push( f[t] );	}}void dfs ( int u, int root ) {
   	if ( vis[u] )		return;	vis[u] = 1;	ans[root] += orz[u];	q.push( u );	dfs ( f[u], root );}void circle () {
   	for ( int i = 1;i <= n;i ++ )		if ( d[i] && ! vis[i] ) {
   			dfs ( i, i );			while ( ! q.empty() ) {
   				int t = q.front();				q.pop();				ans[t] = ans[i];			}		}}int main() {
   	scanf ( "%d", &n );	for ( int i = 1;i <= n;i ++ )		scanf ( "%d", &orz[i] );	for ( int i = 1;i <= n;i ++ ) {
   		scanf ( "%d", &f[i] );		d[f[i]] ++;	}	Top_sort ();	circle ();	while ( ! sta.empty() ) {
   		int t = sta.top();		sta.pop();		ans[t] = orz[t] + ans[f[t]];	}	for ( int i = 1;i <= n;i ++ )		printf ( "%d\n", ans[i] );	return 0;}
     
    
   

就这样就能AC，所以为什么我的tarjan不可以，啊啊啊啊！！！

转载地址：http://ntil.baihongyu.com/