评测记录

但是我按照这个帖子说的把有向边改成无向边就变成 WA on #3,#4,#5,#7

#include<bits/stdc++.h>
using namespace std;
const int N=2e4;

map<int,bool> a[N];
vector<int> g[N],g2[N];
stack<int> s; queue<int> q;

bool in_stack[N];
int n,m,ans,in[N],d[N],dis[N];
int cnt,tot,dfn[N],low[N],id[N];

void tarjan(int u)
{
	dfn[u]=low[u]=(++tot);
	s.push(u),in_stack[u]=true;
	for (int v:g[u])
	{
		if (!dfn[v]) {
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if (in_stack[v])
			low[u]=min(low[u],dfn[v]);
	}
	if (dfn[u]==low[u])
	{
		int x;
		cnt++;
		do {
			x=s.top(),s.pop();
			in_stack[x]=false;
			dis[cnt]+=d[x];
			id[x]=cnt;
		}while (x!=u);
	}
}
void topo()
{
	for (int i=1;i<=cnt;i++)
		if (!in[i])
			q.push(i);
	while (!q.empty())
	{
		int u=q.front();q.pop();
		ans=max(ans,dis[u]);
		for (int v:g2[u])
		{
			in[v]--;
			dis[v]+=dis[u];
			if (!in[v]) q.push(v);
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) {
		scanf("%d",&d[i]);
	}
	while (m--) {
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
	}
	for (int i=1;i<=n;i++)
		if (!dfn[i])
			tarjan(i);
	for (int u=1;u<=n;u++)
		for (int v:g[u]) {
			int x=id[u],y=id[v];
			if (x!=y&&a[x].find(y)==a[x].end()) { //重新建图+map判重边
				in[y]++,a[x][y]=true;
				g2[x].push_back(y);
			}
		}
	topo();
	printf("%d",ans);
	return 0;
}