点击打开链接poj 1986
思路:LCA+Tarjan离线算法+并查集
分析:
1 LCA指的是一棵有根树上两个点的最近公共祖先,或者指的是图上两个点的最短路径。
2 这一题的边数最大40000,还有k(k<=10000)次询问,如果利用最短路的算法肯定TLE。所以这个时候我们选择LCA,假设dis[x]是x到根节点的路径长度,那么(i , j)两点的最短路径为dis[i]+dis[j]-2*dis[LCA(i , j)];LCA(i , j)指的是i,j的最近公共祖先。
3 由于输入的是一个无向图,这个时候根节点是不固定的,所以保存的时候注意保存两次。然后只要随便选取一个作为根节点进行LCA即可(习惯把1作为根节点)
4 使用的是邻阶表存储无向图,注意数组的大小,不然会RE
代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define MAXN 100010
int n , m , k;
int ancestor[MAXN];
int father[MAXN];
int first[MAXN];
int next[MAXN];
int dis[MAXN];
int vis[MAXN];/*标记点是否被处理过*/
vector<int>v[MAXN];
struct Edge{
int x;
int y;
int value;
int ans;
}e[MAXN] , q[MAXN];/*保存读入的边和询问的边*/
/*初始化*/
void init(){
for(int i = 1 ; i <= n ; i++){
father[i] = i;
v[i].clear();
}
memset(ancestor , 0 , sizeof(ancestor));
memset(first , -1 , sizeof(first));
memset(next , -1 , sizeof(next));
memset(dis , 0 , sizeof(dis));
memset(vis , 0 , sizeof(vis));
}
/*并查集的查找*/
int find_Set(int x){
if(x != father[x])
father[x] = find_Set(father[x]);
return father[x];
}
/*并查集的合并*/
void union_Set(int x , int y){
int root_x = find_Set(x);
int root_y = find_Set(y);
father[root_x] = root_y;
}
/*Tarjan算法*/
void LCA(int u){
ancestor[u] = u;
vis[u] = 1;/*标记为处理过*/
for(int i = first[u] ; i != -1 ; i = next[i]){
if(!vis[e[i].y]){/*找到没被处理过的点*/
dis[e[i].y] = dis[u] + e[i].value;/*更新dis数组*/
LCA(e[i].y);/*继续搜索子树*/
union_Set(e[i].y , u);/*合并*/
ancestor[find_Set(e[i].y)] = u;/*当前节点为子树的祖先*/
}
}
/*处理和u 和 v[u][i]有关的询问*/
for(int i = 0 ; i < v[u].size() ; i++){
if(vis[v[u][i]]){
for(int j = 0 ; j < k ; j++){
if(q[j].x == u && q[j].y == v[u][i] || q[j].x == v[u][i] && q[j].y == u)
q[j].ans = father[find_Set(v[u][i])];
}
}
}
}
int main(){
char c;
while(scanf("%d%d" , &n , &m) != EOF){
init();
for(int i = 0 ; i < m ; i++){
scanf("%d %d %d %c" , &e[i].x , &e[i].y , &e[i].value , &c);
/*邻阶表存储无向图*/
e[i+m].x = e[i].y;
e[i+m].y = e[i].x;
e[i+m].value = e[i].value;
next[i] = first[e[i].x];
first[e[i].x] = i;
next[i+m] = first[e[i+m].x];
first[e[i+m].x] = i+m;
}
scanf("%d" , &k);
for(int i = 0 ; i < k ; i++){
scanf("%d%d" , &q[i].x , &q[i].y);
v[q[i].x].push_back(q[i].y);
v[q[i].y].push_back(q[i].x);
}
LCA(1);/*1作为根节点求LCA*/
for(int i = 0 ; i < k ; i++){
int tmp = dis[q[i].x]+dis[q[i].y]-2*dis[q[i].ans];
printf("%d\n" , tmp);
}
}
return 0;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告
北大POJ2305-Basic remains POJ2305-Basic remains