缩点tarjan+记忆化搜索,样例通过求调
查看原帖
缩点tarjan+记忆化搜索,样例通过求调
546830
XSean楼主2023/5/25 08:58

我觉得是我的tarjan写错了,帮忙看看,谢谢啦

#include <bits/stdc++.h>

#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define pre(i, a, b) for(int i = (a); i >= (b); i--)
#define Ede(i, u) for(int i = h[u]; i; i = ne[i])
#define go(i, a) for(auto i : a)
//#define int long long
#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>
#define PIL pair<int, long long>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define mp make_pair
#define eb emplace_back
#define opb pop_back
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define sf scanf
#define prf printf
#define el putchar('\n')
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define mmc(arr1, arr2) memcpy(arr1, arr2, sizeof(arr2))
#define Db(x) prf("test(%s): ", x)
const int inf = 0x3f3f3f3f;

template <typename T> inline void rd(T &x){
	x = 0; bool f = true; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') f = false; ch = getchar();}
	while(ch >= '0' && ch <= '9'){ x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar();}
	if(!f) x = -x;
}
template <typename T, typename ...Args> inline void rd(T &x, Args &...args){ rd(x); rd(args...);}

using namespace std;

const int N = 1e4 + 10, M = 1e5 + 10;
int n, m;
int h[N], e[M], ne[M], idx;
PII edge[M];
void add(int a, int b){
	e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}
int w[N];
int dfn[N], low[N], tot;
//dfn时间戳, low节点i能到达的最小的时间戳, 目的为了不提前弹出栈 
int stk[N], instk[N], top;
int scc[N], sum[N], cnt;
void tarjan(int u){
	dfn[u] = low[u] = ++tot;
	stk[++top] = u, instk[u] = 1;
	//计算low,递归 
	Ede(i, u){
		int v = e[i];
		if(!dfn[v]){
			tarjan(v);
			low[u] = min(low[u], dfn[v]); 
		}else if(instk[v]){
			low[u] = min(low[u], dfn[v]);
		}
	}
	//删块 
	if(dfn[u] == low[u]){
		int v; ++cnt;
		do{
			v = stk[top--], instk[v] = 0;
			scc[v] = cnt;
			sum[cnt] += w[v];
		}while(u != v);
	} 
}
int f[N];
void dfs(int u){
	if(f[u]) return;
	f[u] = sum[u];
	int maxa = 0;
	Ede(i, u){
		int v = e[i];
		if(!f[v]) dfs(v);
		maxa = max(maxa, f[v]);
	} 
	f[u] += maxa;
}
int main(){
	/*
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
	*/
	rd(n, m);
	rep(i, 1, n) rd(w[i]);
	rep(i, 1, m){
		int x, y; rd(x, y);
		edge[i] = {x, y};
		add(x, y);
	}
	rep(i, 1, n) if(!dfn[i]) tarjan(i);
	for(int i = 1; i <= cnt; i++) printf("%d\n", sum[i]);
	mms(h, 0), mms(e, 0), mms(ne, 0), idx = 0;
	rep(i, 1, m){
		int x = edge[i].fi, y = edge[i].se;
		if(scc[x] != scc[y]){
			add(scc[x], scc[y]);
		}
	}
	int ans = 0;
	rep(i, 1, cnt){
		if(!f[i]){
			dfs(i);
			ans = max(ans, f[i]);	
		}
	}
	prf("%d\n", ans); 
	return 0;
}
2023/5/25 08:58
加载中...