本文主要是介绍BZOJ 1787 [Ahoi2008]Meet紧急集合 题解与分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
[Ahoi2008]Meet 紧急集合
Description
Input
Output
Sample Input
6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6
Sample Output
5 2
2 5
4 1
6 0
HINT
【分析】：
这里用的是Tarjan离线求LCA，详细解析此算法请点击：http://blog.csdn.net/csyzcyj/article/details/10051173
转换成抽象模型，就是要求一棵树（N个点，有N-1条边表示这个图是棵树）中某一点满足给定三点a，b，c到某一点的距离和最小。那么我们想到最近公共祖先的定义，推出只有集合点在LCA(a,b)、LCA(a,c)、LCA(b,c)中，才能保证距离和最近，并且这三个值中的两个必定相等， 那么另一个就是所求的集合点。假定LCA(a,b)就是集合点，那么最后的答案就是dist[a]+dist[b]+dist[c]-dist[LCA(a,b)]-2*dist[LCA(a,b),c]<dist[x]表示x到树的根节点的距离>，如下图就是个例子。
【测评信息】：
Time:3620 ms ，Memory:79896 kb
【时间复杂度分析】：
Tarjan离线O(N+3*M)+O(N+M)
【代码】：
/**************************************************************
Problem: 1787
Language: C++
Result: Accepted
Time:3620 ms
Memory:79896 kb
****************************************************************/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define MAXEDGE 3000030
#define MAXPOINT 1000010
#define MAXN 500001
#define MAXM 500001
struct EDGE{int to,v,next;};
struct QUESTION{int to,num,next;};
EDGE a[MAXPOINT];
QUESTION b[MAXEDGE];
int N,M,edge[MAXN],question[MAXN],tot1=0,tot2=0,ansf[MAXM],anst[MAXM],q[MAXM][3],S[MAXM];
int fa[MAXN],LCA[MAXEDGE],dist[MAXN];
bool vis[MAXN];
inline void add_edge(int x,int y,int value)
{
a[++tot1].to=y;
a[tot1].v=value;
a[tot1].next=edge[x];
edge[x]=tot1;
}
inline void add_question(int x,int y,int number)
{
b[++tot2].to=y;
b[tot2].num=number;
b[tot2].next=question[x];
question[x]=tot2;
}
inline int get(int x)
{
if(fa[x]==x) return x;
return fa[x]=get(fa[x]);
}
inline void Tarjan(int x)
{
fa[x]=x;
vis[x]=true;
for(int i=question[x];i;i=b[i].next)
{
int now_to=b[i].to;
if(vis[now_to])
LCA[b[i].num]=get(now_to);
}
for(int i=edge[x];i;i=a[i].next)
{
int now_to=a[i].to;
if(!vis[now_to])
{
dist[now_to]=dist[x]+a[i].v;
Tarjan(now_to);
fa[now_to]=x;
}
}
}
int main()
{
//freopen("input.in","r",stdin);
//freopen("output.out","w",stdout);
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++)
fa[i]=i;
for(int i=1;i<=N-1;i++)
{
int A,B;
scanf("%d%d",&A,&B);
add_edge(A,B,1);
add_edge(B,A,1);
}
for(int i=1;i<=3*M;i+=3)
{
int A,B,C;
scanf("%d%d%d",&A,&B,&C);
q[(i+2)/3][0]=A;
q[(i+2)/3][1]=B;
q[(i+2)/3][2]=C;
add_question(A,B,i);
add_question(B,A,i);
add_question(A,C,i+1);
add_question(C,A,i+1);
add_question(B,C,i+2);
add_question(C,B,i+2);
}
Tarjan(1);
memset(vis,false,sizeof(vis));
memset(b,0,sizeof(b));
memset(question,0,sizeof(question));
for(int i=1;i<=N;i++)
fa[i]=i;
tot2=0;
for(int i=1;i<=3*M;i+=3)
{
int A=q[(i+2)/3][0],B=q[(i+2)/3][1],C=q[(i+2)/3][2];
S[(i+2)/3]=dist[A]+dist[B]+dist[C];
if(LCA[i]==LCA[i+1])
{
add_question(LCA[i+2],A,(i+2)/3);
add_question(A,LCA[i+2],(i+2)/3);
ansf[(i+2)/3]=LCA[i+2],anst[(i+2)/3]=A;
}
else if(LCA[i]==LCA[i+2])
{
add_question(LCA[i+1],B,(i+2)/3);
add_question(B,LCA[i+1],(i+2)/3);
ansf[(i+2)/3]=LCA[i+1],anst[(i+2)/3]=B;
}
else if(LCA[i+1]==LCA[i+2])
{
add_question(LCA[i],C,(i+2)/3);
add_question(C,LCA[i],(i+2)/3);
ansf[(i+2)/3]=LCA[i],anst[(i+2)/3]=C;
}
}
memset(LCA,0,sizeof(LCA));
Tarjan(1);
for(int i=1;i<=M;i++)
printf("%d %d\n",ansf[i],S[i]-dist[ansf[i]]-2*dist[LCA[i]]);
//system("pause");
return 0;
}
转载注明出处：http://blog.csdn.net/u011400953
这篇关于BZOJ 1787 [Ahoi2008]Meet紧急集合 题解与分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
