tarjan用暴搜做
查看原帖
tarjan用暴搜做
250699
mot1ve楼主2020/8/11 21:40

TLE是理所应当的,不过为什么不超时的WA了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int maxn,ans,n,m;
int w[100010],head[100010];
struct node{
	int to,nxt;
}edge[100010];
bool vis[100010];
int idx;
void add(int u,int v)
{
	edge[++idx].nxt=head[u];
	edge[idx].to=v;
	head[u]=idx;
}
void dfs(int x,int sum)
{
	vis[x]=1;
	for(int i=head[x];i;i=edge[i].nxt)
	{
		int v=edge[i].to;
		if(vis[v])
		continue;
		ans=max(ans,sum+w[v]);
		dfs(v,sum+w[v]);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&w[i]);
	}
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	for(int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof(vis));
		dfs(i,w[i]);
		maxn=max(ans,maxn);
		ans=0;
	}
	cout<<maxn;
	return 0;
}
10 20
970 369 910 889 470 106 658 659 916 964 
3 2
3 6
3 4
9 5
8 3
5 8
9 1
9 7
9 8
7 5
3 7
7 8
1 7
10 2
1 10
4 8
2 6
3 1
3 5
8 5

6911
2020/8/11 21:40
加载中...