Least Common Ancestors 分类： ACM TYPE 2014-10-19 11:24 84人阅读 评论(0) 收藏

时间：2023-12-29 15:36:02
#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <vector>

using namespace std;

struct node

{

	int f, s;

};

vector<node>imap[40005];

int deep[40005];

int dis[40005];

int fa[40005];

int ffa[40005];

bool vis[40005];

void dfs(int n,int s,int ff)

{

	vis[n] = true;

	for(int i=0;i<imap[n].size();i++)

	{

		if(vis[imap[n][i].f])		continue;

		deep[imap[n][i].f] = s;

		dis[imap[n][i].f] = dis[n]+imap[n][i].s;

		fa[imap[n][i].f] = n;

		ffa[imap[n][i].f] = ff;

		dfs(imap[n][i].f,s+1,ff);

	}

}

int lca(int x, int y)

{

	if(x==y)	return dis[x];

	if(deep[x]>=deep[y])	return lca(fa[x],y);

	else return lca(x,fa[y]);

}

int main()

{

	int t, n, m, c;

	int u, v, s, ans;

	node cur;

	while(scanf("%d%d%d",&n,&m,&c)!=EOF)

	{

		memset(vis,false,sizeof(vis));

		memset(fa,0,sizeof(fa));

		memset(fa,false,sizeof(fa));

		memset(dis,0,sizeof(dis));

		memset(deep,false,sizeof(deep));

		memset(imap,0,sizeof(imap));

		for(int i=0;i<m;i++)

		{

			scanf("%d%d%d",&u,&v,&s);

			cur.f = v;

			cur.s = s;

			imap[u].push_back(cur);

			cur.f = u;

			imap[v].push_back(cur);

		}

		for(int i=1;i<=n;i++)

		{

			if(vis[i])	continue;

			ffa[i] = i;

			dfs(i,1,i);

		}

		for(int i=0;i<c;i++)

		{

			scanf("%d%d",&u,&v);

			if(ffa[u]!=ffa[v])	printf("Not connected\n");

			else

			{

				ans = lca(u,v);

				printf("%d\n",dis[u]+dis[v]-2*ans);

			}

		} 

	}

	return 0;

}

来自HDU2847

版权声明：本文为博主原创文章，未经博主允许不得转载。

相关文章