递归和防爆栈都MLE了求助(还专门开小了空间,但前面几个点都过不了)
查看原帖
递归和防爆栈都MLE了求助(还专门开小了空间,但前面几个点都过不了)
301029
rustleinthewind楼主2022/8/28 06:50
#include<iostream>
#include<cstdio>
using namespace std;
bool vis[10000]={false};//标记访问 
bool k[10000]={false};//标记是否感谢答案 
bool cir[10000]={false};//标记是否在环上
bool ok=false;//是否找到环 
long long no[10000];//标记第i号结点不用访问的边的权值,最终输出为sum-no[i] 
int n;
int minx; 
int nw;//遍历环时记录环上结点 
int a,b,c,d;//输入处理 
int s[20000],tp=1;//栈和栈顶 
long long sum=0;//边权和 
int head[10000]={0},tar[10000]={0},cnt=1;
struct edge
{
	int to,nex,w,p;
}e[20000];//链式前向星存无向图,切记! 
void add(int from,int t,int weig,int beau)//加边 
{
	e[cnt].to=t;
	e[cnt].w=weig;
	e[cnt].p=beau;
	e[cnt].nex=head[from];
	head[from]=cnt;
	tar[from]=cnt;
	cnt++;
	return;
}
bool dfs()//找环 
{
	int i,j;
	while(tp>0)//若栈非空 
	{
		i=tar[s[tp]];//i表示当前栈顶结点的下一条边 
		j=e[i].to;//j表示这条边对应的结点
//		cout<<s[1]<<s[2]<<s[3]<<s[4]<<endl;
		if(i==0)//当前栈顶结点所有相连的子节点已经全部访问完了,出栈
		{
			--tp;
			continue;
		}
		if(tp>1&&j==s[tp-1]) //防止双向边被误认为环
		{
			tar[s[tp]]=e[i].nex;//更新tar值删边
			continue;
		}
		if(vis[j]==true)//找到环了 
		{
			cir[j]=true;//标记下一个节点在环上
			do
			{
				cir[s[tp]]=true;//标记当前栈顶节点在环上
				--tp;//出栈
			}while(s[tp]!=j);
			
			break;//已经成功找到环了,结束 
			break;//已经成功找到环了,结束 
		}
		else//没找到环,访问下一个结点 
		{
			tar[s[tp]]=e[i].nex;//更新tar值删边 
			vis[j]=true;//标记访问
			++tp;
			s[tp]=j;
		}
	}
	/* 
	for(int i=head[rt];i!=0;i=e[i].nex)//遍历 
	{
		if(ok==true) return;//找到环直接回溯
		if(e[i].to==fa) continue;
		if(vis[e[i].to]==true)//找到环了 
		{
			cir[e[i].to]=true;//标记当前节点在环上
			do
			{
				cir[s[tp]]=true;//标记当前节点在环上
				tp--;//出栈
			}while(s[tp]!=e[i].to);
			ok=true;
			return;
		}
		else//没找到环,继续遍历 
		{
			dfs(e[i].to,rt); 
		}
	}
	--tp;//出栈
	return;
	*/ 
}
void ans(int rt)//更新答案
{
	
	for(int i=head[rt];i!=0;i=e[i].nex)//遍历 
	{
		if(k[e[i].to]==false&&cir[e[i].to]==false)
		{
			k[e[i].to]==true;
			no[e[i].to]=no[rt];
			ans(e[i].to);
		}
	}
	return;
} 
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d%d%d%d",&a,&b,&c,&d);
		sum+=c;//累加 
		add(a,b,c,d);
		add(b,a,c,d);
	}
	s[1]=1;
	vis[1]=true;
//	dfs();//找环
	int i,j;
	while(tp>0)//若栈非空 
	{
		i=tar[s[tp]];//i表示当前栈顶结点的下一条边 
		j=e[i].to;//j表示这条边对应的结点
		if(i==0)//当前栈顶结点所有相连的子节点已经全部访问完了,出栈
		{
			--tp;
			continue;
		}
		if(tp>1&&j==s[tp-1]) //防止双向边被误认为环
		{
			tar[s[tp]]=e[i].nex;//更新tar值删边
			continue;
		}
		if(vis[j]==true)//找到环了 
		{
			cir[j]=true;//标记下一个节点在环上
			do
			{
				cir[s[tp]]=true;//标记当前栈顶节点在环上
				--tp;//出栈
			}while(s[tp]!=j);
			
			break;//已经成功找到环了,结束 
			break;//已经成功找到环了,结束 
		}
		else//没找到环,访问下一个结点 
		{
			tar[s[tp]]=e[i].nex;//更新tar值删边 
			vis[j]=true;//标记访问
			++tp;
			s[tp]=j;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(cir[i]==true)//对于每个环上结点 
		{
			minx=1e9+7;
			for(int j=head[i];j!=0;j=e[j].nex)//计算出它的答案 
			{
				if(cir[e[j].to]==true&&e[j].p<minx)//找到美观度更小的环边,这条不走了 
				{
					minx=e[j].p;
					no[i]=e[j].w;
				}
			}
			k[i]=true;
			ans(i);//并为以它根的子树上的所有结点更新答案 
		}
	}
	for(int i=1;i<=n;i++) printf("%lld\n",sum-no[i]);
	return 0;
}
2022/8/28 06:50
加载中...