MLE求助
查看原帖
MLE求助
343245
Bigfish_楼主2022/9/23 21:28

如题,应该是递归有问题?

#include <bits/stdc++.h>//MLE
using namespace std;
int n,d[1000005],num=1,head[1000005];
int u1,u2;
long long ans=0;
struct edge
{
	int from,to;
	int last;
}a[1000005];
void yadd(int from,int to)
{
	a[num].from=from;
	a[num].to=to;
	a[num].last=head[from];
	head[from]=num;
	num++;
}

bool vis[1000005];
int o,o1;
void ydfs(int u)//找环上任意两点 
{
	vis[u]=1;
	for(int t=head[u];t;t=a[t].last)
	{
		int y=a[t].to;
		if(vis[y]==0)
			ydfs(y);
		else
			o=t;
	}
	return ;
}

int tree[1000005][2],p1,p2;//0为不选,1为选 
void ytreesearch(int u)//树型dp 
{
	tree[u][0]=0;
	tree[u][1]=d[u];
	for(int t=head[u];t;t=a[t].last)
	{
		int y=a[t].to;
		if(t==o)
		{
			tree[y][1]=-999;
		} 
		else
		{
			ytreesearch(y);
			tree[u][0]+=max(tree[y][1],tree[y][0]);
			tree[u][1]+=tree[y][0];
		}
	}
	return ;
}
int main()
{
	scanf("%d",&n);
	for(int t=1;t<=n;t++)
	{
		scanf("%d%d",&d[t],&u2);
		yadd(t,u2);
	}
	for(int t=1;t<=n;++t)
	{
		if(vis[t]) continue;
		p1=0;p2=0;
		ydfs(t);
		
		o1=a[o].from;//o为删去的边 
		ytreesearch(o1);
		p1=max(tree[o1][1],tree[o1][0]);
		
		o1=a[o].to;
		ytreesearch(o1);
		p2=max(tree[o1][1],tree[o1][0]);
		
		ans+=max(p1,p2);
	}
	printf("%d",ans);
	return 0;
}
2022/9/23 21:28
加载中...