HDU2874 Connections between cities
? 解题记录 ? ? HDU ? ? 并查集 ? ? 倍增 ? ? 补档计划第一期 ?    2018-01-28 11:12:33    366    0    0

 

After World War X, a lot of cities have been seriously damaged, and we need to rebuild those cities. However, some materials needed can only be produced in certain places. So we need to transport these materials from city to city. For most of roads had been totally destroyed during the war, there might be no path between two cities, no circle exists as well.
Now, your task comes. After giving you the condition of the roads, we want to know if there exists a path between any two cities. If the answer is yes, output the shortest path between them.

InputInput consists of multiple problem instances.For each instance, first line contains three integers n, m and c, 2<=n<=10000, 0<=m<10000, 1<=c<=1000000. n represents the number of cities numbered from 1 to n. Following m lines, each line has three integers i, j and k, represent a road between city i and city j, with length k. Last c lines, two integers i, j each line, indicates a query of city i and city j.OutputFor each problem instance, one line for each query. If no path between two cities, output “Not connected”, otherwise output the length of the shortest path between them.Sample Input

5 3 2
1 3 2
2 4 3
5 2 3
1 4
4 5

Sample Output

Not connected
6

本题其实就是维护森林上的倍增LCA。对于每一棵树维护倍增信息。对于整个森林我们用并查集维护一下连通性就可以了。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=20000+100;
const int max2=20;
struct edge
{
	int v,w;
	int next;
}e[maxn*2];

int head[maxn];
int fa[maxn];
int d[maxn];
bool vis[maxn];
int dc[maxn];
int p[maxn][max2+5];
int n,m,qn;
int edk;

void init(int n)
{
	for(int i=1;i<=n;i++)
		fa[i]=i;
}

int find(int a)
{
	if(fa[a]==a) return a;
	return fa[a]=find(fa[a]);
}

void combine(int a,int b)
{
	a=find(a);
	b=find(b);
	fa[a]=b;
}

void adde(int u,int v,int w)
{
	e[++edk].w=w;
	e[edk].v=v;
	e[edk].next=head[u];
	head[u]=edk;
}

void dfs(int u,int fa,int ec)
{
	d[u]=d[fa]+1;
	dc[u]=dc[fa]+ec;
	p[u][0]=fa;
	for(int i=1;i<=max2;i++)
		p[u][i]=p[p[u][i-1]][i-1];
	
	for(int i=head[u];i!=-1;i=e[i].next)
	{
		int v=e[i].v;
		if(v!=fa)
			dfs(v,u,e[i].w);
	}
}

int lca(int a,int b)
{
	if(d[a]<d[b]) swap(a,b);
	for(int i=max2;i>=0;i--)
		if(d[a]-(1<<i)>=d[b])
			a=p[a][i];

	if(a==b) return a;
	for(int i=max2;i>=0;i--)
		if(p[a][i]!=p[b][i])
			{
				a=p[a][i];
				b=p[b][i];
			}
	return p[a][0];
}

int main()
{
	while(scanf("%d%d%d",&n,&m,&qn)==3)
	{
		memset(vis,0,sizeof(vis));
		memset(p,0,sizeof(p));
		memset(d,0,sizeof(d));
		memset(dc,0,sizeof(dc));
		memset(head,-1,sizeof(head));
		edk=0;
		init(n);
		for(int i=1;i<=m;i++)
			{
				int a,b,c;
				scanf("%d%d%d",&a,&b,&c);
				adde(a,b,c);
				adde(b,a,c);
				combine(a,b);
			}
		for(int i=1;i<=n;i++)
		if(!vis[find(i)])
		{
			vis[find(i)]=1;
			dfs(i,0,0);
		}
		for(int i=1;i<=qn;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			if(find(a)!=find(b))
				{
					printf("Not connected\n");
					continue;
				}
			int t=lca(a,b);
			printf("%d\n",dc[a]-dc[t]+dc[b]-dc[t]);
		}
	}
	return 0;
}

 


 

上一篇: 洛谷P1471 方差

下一篇: BZOJ1036: [ZJOI2008]树的统计Count

366 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航