hdu 2874 森林上任意两点的之间的最短距离

最新推荐文章于 2020-03-01 20:47:50 发布

四光年

最新推荐文章于 2020-03-01 20:47:50 发布

阅读量210

点赞数

分类专栏：树

本文链接：https://blog.csdn.net/qq_41755258/article/details/97382657

版权

树专栏收录该内容

6 篇文章

订阅专栏

博主分享了在解决LCA模板题过程中遇到的各种问题及解决方法。从树剖到Tarjan离线算法，再到内存和时间优化，最终发现是由于变量引用错误导致的效率瓶颈。文章记录了这一系列的调试过程，对于理解LCA算法及其优化技巧有很好的参考价值。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

lca模板题，tle了一上午。先用树剖，tle。再用targin离线搞是mle。。。优化了半天终于不mle了，又变成tle。。。最后发现是add函数ans变量没有写&，擦。以后长记性了

#include <bits/stdc++.h>
using namespace std;
#define res register int
#define ll long long
const int maxn=1e4+5;
const int maxn1=1e6+5;
struct edge{
	int to,next,v;
}e[maxn*2],qe[maxn1*2];
int head[maxn],qhead[maxn],ans,qans,vis[maxn],fa[maxn];
int out[maxn1],dis[maxn];
int N,M,q;
void add(edge e[],int head[],int x,int y,int v,int &ans){
	e[ans].to=y;
	e[ans].next=head[x];
	e[ans].v=v;
	head[x]=ans++;
}

int find(int x){
	return x==fa[x]?x:(fa[x]=find(fa[x]));
}

void dfs(int x,int deep,int root){ 
 	fa[x]=x;
	vis[x]=root;
	dis[x]=deep;
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;
		if(!vis[y]){
			dfs(y,deep+e[i].v,root);
			fa[y]=x;
		}
	} 
	for(int i=qhead[x];i;i=qe[i].next){
		int y=qe[i].to;
		if(root==vis[y]){
			int pos=qe[i].v;
			out[pos]=dis[x]+dis[y]-2*dis[find(y)];
		}
	}
}

void init(){
	memset(head,0,sizeof(head));
	memset(qhead,0,sizeof(qhead));
	memset(vis,0,sizeof(vis));
	ans=1;
	qans=1;
}

int main()
{
//	freopen("input.txt", "r", stdin);
	while(~scanf("%d%d%d",&N,&M,&q)){
		init();
		for(int i=0,a,b,v;i<M;i++){
			scanf("%d%d%d",&a,&b,&v);
			add(e,head,a,b,v,ans);
			add(e,head,b,a,v,ans);
		}
		for(int i=1,a,b;i<=q;i++){
			scanf("%d%d",&a,&b);
			out[i]=-1;
			add(qe,qhead,a,b,i,qans);
			add(qe,qhead,b,a,i,qans);
		}
		for(int i=1;i<=N;i++){
			if(!vis[i]){
				dfs(i,0,i);
			}
		}
		for(int i=1;i<=q;i++){
			if(-1==out[i]) printf("Not connected\n");
			else printf("%d\n",out[i]);
		} 
	}
	return 0;
}