魔法RE
查看原帖
魔法RE
297831
idgg007楼主2023/7/12 20:33

这是一段带有魔法的代码,他会在程序执行结束时RE,尽管程序输出是正确的:记录

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<list>
using namespace std;
struct Edge {
	int to;
	Edge*nextEdge;
};
int N, M, DFSIndex;
queue<int>Que;
vector<int>in;
vector<int>A;
vector<Edge*>head;
vector<int>visited;
vector<bool>inST;
vector<int>DFN;
vector<int>oldToNew;
vector<int>sum;
stack<int>record;
list<Edge>edge;
list<Edge>newGraph;
vector<Edge*>newHead;
vector<int>DP;
inline void Tarjan(const int&n, const int&deepth) {
	visited[n] = ++DFSIndex;
	inST[n] = 1;
	record.push(n);
	for (Edge*i = head[n]; i; i = i->nextEdge) {
		if (!visited[i->to]) {
			Tarjan(i->to, deepth + 1);
			DFN[n] = min(DFN[n], DFN[i->to]);
		} else {
			if (inST[i->to]) {
				DFN[n] = min(visited[i->to], DFN[n]);
			}
		}
	}
	if (visited[n] == DFN[n]) {
		while (record.top() != n) {
			oldToNew[record.top()] = newHead.size();
			sum[oldToNew[record.top()]] += A[record.top()];
			inST[record.top()] = 0;
			record.pop();
		}
		oldToNew[record.top()] = newHead.size();
		sum[oldToNew[record.top()]] += A[record.top()];
		inST[record.top()] = 0;
		record.pop();
		newHead.push_back(NULL);
	}
}
inline void AddNewEdge(const int&from, const int&to) {
	newGraph.push_back({to, newHead[from]});
	newHead[from] = &newGraph.back();
}
inline void AddEdge(const int&from, const int&to) {
	edge.push_back({to, head[from]});
	head[from] = &edge.back();
}
void F() {
	while (!Que.empty()) {
		int node = Que.front();
		for (Edge*i = newHead[node]; i; i = i->nextEdge) {
			DP[i->to] = max(DP[i->to],DP[node]+sum[i->to]);
			in[i->to]--;
			if(!in[i->to]){
				Que.push(i->to);
			}
		}
		Que.pop();
	}
}
int main() {
	//ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> M;
	sum.assign(N + 1, 0);
	DFN.assign(N + 1, 0x3f3f3f3f);
	oldToNew.assign(N + 1, 0);
	A.assign(N + 1, 0);
	visited.assign(N + 1, 0);
	head.assign(N + 1, NULL);
	newHead.push_back(NULL);
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
	}
	for (int i = 1; i <= M; i++) {
		int a, b;
		cin >> a >> b;
		AddEdge(a, b);
	}
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			inST.assign(N + 1, 0);
			while(!record.empty()){
				record.pop();
			}
			Tarjan(i, 0);
		}
	}
	in.assign(newHead.size(), 0);
	DP.assign(newHead.size(), 0);
	for (int i = 1; i <= N; i++) {
		DP[i] = sum[i];
		for (Edge*j = head[i]; j; j = j->nextEdge) {
			if (oldToNew[i] != oldToNew[j->to]) {
				AddNewEdge(oldToNew[i], oldToNew[j->to]);
				in[j->to]++;
			}
		}
	}
	cout<<"1\n";
	for (int i = 1; i < newHead.size(); i++) {
		if (!in[i]) {
			Que.push(i);
		}
	}
	F();
	int Ans=0;
	for(int i=1;i<newHead.size();i++){
		Ans=max(DP[i],Ans);
	}
	cout<<Ans<<"\n";
   return 0;
}
2023/7/12 20:33
加载中...