数据范围不是1e4和1e5吗?
查看原帖
数据范围不是1e4和1e5吗?
520544
Phrvth楼主2023/7/14 20:26

为啥我 MAXN=1e4+7,MAXM=1e5+7 会re8个点

但是乘了十之后就过了

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 7, MAXM = 1e6 + 7;

struct Node {
	int nxt, to;
}Edge[MAXM];

int H[MAXN], E_cnt;

void add(int from, int to) {
	Edge[++ E_cnt] = Node{H[from], to};
	H[from] = E_cnt;
}

int n, m, Value[MAXN];

int Dfn[MAXN], Low[MAXN], Scc[MAXN], scc, cnt;

bool V[MAXN];

int Sum[MAXN];

stack <int> T;

void tarjan(int u) {
	Dfn[u] = ++ cnt; Low[u] = Dfn[u]; 
	V[u] = true; T.push(u);
	for (int i = H[u]; i; i = Edge[i].nxt) {
		int v = Edge[i].to;
		if (!Dfn[v]) tarjan(v), Low[u] = min(Low[u], Low[v]);
		else if (V[v]) Low[u] = min(Low[u], Low[v]);
	} 
	if (Dfn[u] == Low[u]) {
		Scc[u] = ++ scc; Sum[scc] = Value[u];
		while (!T.empty() && T.top() != u) V[T.top()] = 0, Scc[T.top()] = scc, Sum[scc] += Value[T.top()], T.pop();
		T.pop(); V[u] = 0;
	}
}

int X[MAXN], Y[MAXN], In[MAXN], ans, Dp[MAXN];

int topu() {
	queue <int> Q;
	for (int i = 1; i <= scc; i ++) {
		if (!In[i]) Q.push(i);
	}
	while (!Q.empty()) {
		int now = Q.front(); Q.pop();
		Dp[now] += Sum[now];
		for (int i = H[now]; i; i = Edge[i].nxt) {
			int v = Edge[i].to;
			Dp[v] = max(Dp[v], Dp[now]);
			if (-- In[v] == 0) Q.push(v);
		}
		ans = max(ans, Dp[now]);
	}
	return ans;
}

int main () {
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) cin >> Value[i];
	for (int i = 1; i <= m; i ++) {
		cin >> X[i] >> Y[i]; add(X[i], Y[i]);
	}
	for (int i = 1; i <= n; i ++)
		if (!Dfn[i]) tarjan(i);
	
	memset(H, 0, sizeof(H)); E_cnt = 0;
	for (int i = 1; i <= m; i ++) {
		int x = Scc[X[i]], y = Scc[Y[i]];
		if (x == y) continue;
		add(x, y); In[y] ++;
	}
	cout << topu();
	return 0;
}
2023/7/14 20:26
加载中...