提交记录

我尝试了一些数据，但还是不知道是哪里错了

思路就是先 Tarjan 缩点再重新建图进行记忆搜

是有些特殊情况吗？还是思路问题？

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int MN = 100000;
stack <int> stajan;
struct LINK{
	int to;
	int next;
}Link[MN * 100];//存图的
int head[MN];
struct NODE{
	int wei;//点权值
	int dfn;
	int low;
	int sccid;//这个点所在的强连通分量
	ll max_sum;//从这个点出发记忆搜的值
}Node[MN];
int sccsiz[MN], ins[MN * 10], ine[MN * 10];//ins 和 ine 用来存原图
int cntScc = 0, cntLink = 0, cntDfn = 0, N, M;
bool vis[MN];

void add_link(int start, int end){
	Link[++cntLink].to = end;
	Link[cntLink].next = head[start];
	head[start] = cntLink;
}

void Tarjan(int start){
	Node[start].dfn = Node[start].low = ++cntDfn;
	vis[start] = true;
	stajan.push(start);
	for(int i = head[start]; i; i = Link[i].next){
		if( !Node[Link[i].to].dfn ){
			Tarjan(Link[i].to);
			Node[start].low = min(Node[start].low, Node[Link[i].to].low);
		}
		else if(vis[Link[i].to])
			Node[start].low = min(Node[start].low, Node[Link[i].to].dfn);
	}
	if(Node[start].low == Node[start].dfn){
		int now;
		++cntScc;
		do{
			now = stajan.top();
			vis[now] = false;
			stajan.pop();
			Node[now].sccid = cntScc;
			Node[now].low = min(Node[now].low, Node[start].low);
			sccsiz[cntScc] += Node[now].wei;
		}while(start != now);
	}
}

void remS(int node){
	if(Node[node].max_sum)	return;
	Node[node].max_sum = sccsiz[Node[node].sccid];
	ll maxnum = 0;
	for(int i = head[node]; i; i = Link[i].next){
		if( !Node[Link[i].to].max_sum )	remS(Link[i].to);
		maxnum = max(maxnum, Node[Link[i].to].max_sum);
	}
	Node[node].max_sum += maxnum;
}

signed main(){
//	freopen("P3387-2.in","r",stdin);
	scanf("%d%d", &N, &M);
	for(int i = 1; i <= N; i++)
		scanf("%d", &Node[i].wei);
	for(int i = 1, sta, end; i <= M; i++){
		scanf("%d%d", &sta, &end);
		add_link(sta, end);
		ins[i] = sta;
		ine[i] = end;
	}
	for(int i = 1; i <= N; i++)
		if( !Node[i].dfn )
			Tarjan(i);
	cntLink = 0;//清空原图
	memset(head, 0, sizeof(head));
	memset(Link, 0, sizeof(Link));
	for(int i = 1; i <= M; i++)
		if(Node[ins[i]].low != Node[ine[i]].low)
			add_link(ins[i], ine[i]);
	ll ans = 0;
	for(int i = 1; i <= N; i++){
		if( !Node[i].max_sum ){
			remS(i);
			ans = max(ans, Node[i].max_sum);
		}
	}
	printf("%lld", ans);
	return 0;
}