BZOJ 1787 [Ahoi2008]Meet紧急集合 题解与分析

2024-06-07 07:18

本文主要是介绍BZOJ 1787 [Ahoi2008]Meet紧急集合 题解与分析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

[Ahoi2008]Meet 紧急集合

Time Limit: 20 Sec  
Memory Limit: 162 MB
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

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紧急集合 题解与分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1038502

相关文章

Python 迭代器和生成器概念及场景分析

《Python迭代器和生成器概念及场景分析》yield是Python中实现惰性计算和协程的核心工具,结合send()、throw()、close()等方法,能够构建高效、灵活的数据流和控制流模型,这... 目录迭代器的介绍自定义迭代器省略的迭代器生产器的介绍yield的普通用法yield的高级用法yidle

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

kotlin中const 和val的区别及使用场景分析

《kotlin中const和val的区别及使用场景分析》在Kotlin中,const和val都是用来声明常量的,但它们的使用场景和功能有所不同,下面给大家介绍kotlin中const和val的区别,... 目录kotlin中const 和val的区别1. val:2. const:二 代码示例1 Java

Go标准库常见错误分析和解决办法

《Go标准库常见错误分析和解决办法》Go语言的标准库为开发者提供了丰富且高效的工具,涵盖了从网络编程到文件操作等各个方面,然而,标准库虽好,使用不当却可能适得其反,正所谓工欲善其事,必先利其器,本文将... 目录1. 使用了错误的time.Duration2. time.After导致的内存泄漏3. jsO

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3

找不到Anaconda prompt终端的原因分析及解决方案

《找不到Anacondaprompt终端的原因分析及解决方案》因为anaconda还没有初始化,在安装anaconda的过程中,有一行是否要添加anaconda到菜单目录中,由于没有勾选,导致没有菜... 目录问题原因问http://www.chinasem.cn题解决安装了 Anaconda 却找不到 An

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

Spring、Spring Boot、Spring Cloud 的区别与联系分析

《Spring、SpringBoot、SpringCloud的区别与联系分析》Spring、SpringBoot和SpringCloud是Java开发中常用的框架,分别针对企业级应用开发、快速开... 目录1. Spring 框架2. Spring Boot3. Spring Cloud总结1. Sprin

Spring 中 BeanFactoryPostProcessor 的作用和示例源码分析

《Spring中BeanFactoryPostProcessor的作用和示例源码分析》Spring的BeanFactoryPostProcessor是容器初始化的扩展接口,允许在Bean实例化前... 目录一、概览1. 核心定位2. 核心功能详解3. 关键特性二、Spring 内置的 BeanFactory