这是一段带有魔法的代码,他会在程序执行结束时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;
}