「bsoj4767」生成树 - 动态规划+启发式合并并查集 | Bill Yang's Blog

「bsoj4767」生成树 - 动态规划+启发式合并并查集

题目大意

    给出一张无向边带权图$G(V,E)$。并规定对于该图上的每条简单路径,其权值为经过的边权中的次大值。
    现在有$Q$个询问。每个询问给定两个点$A,B$,你要回答所有从$A$到$B$的简单路径中,最小的权值是多少。


题目分析

60pts

二分权值,问题转化为用小于等于$mid$的边和最多一条大于$mid$的边将两点连通,并查集维护小于等于$mid$的边,枚举大于$mid$的边。
时间复杂度$O(n^2\log n)$。

100pts

将边权从小到大排序,从小到大用并查集合并。
并查集每次合并集合的时候,使用启发式合并(不路径压缩,原因后叙述),对被合并集合预处理$f[i,j]$表示第$i$个结点再经过一条更大边到达$j$时的次大边,这可以在Kruskal的过程中预处理出。

若可以快速知道$mid$时并查集中两点的连通情况,就可以根据$f[]$得到次大边。
为了得到$mid$时的并查集两点连通情况,不路径压缩,并查集就长得像一棵树,且满足Kruskal重构树的性质(是一个大根堆),因此就可以通过设定上界在并查集上爬树得到$mid$时的连通情况。

因为$f[i,j]$用数组开不下,但实际总状态量很小,使用maphash来优化空间。
时间复杂度$O(n\log^2 n)$或$O(n\log n)$。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
struct HashTable {
const static int BASE=12369,mod=999599;
struct Point {
int x,y,v;
Point(int _x=0,int _y=0,int _v=0):x(_x),y(_y),v(_v) {}
};
vector<Point>a[mod];
void insert(int x,int y,int v) {
if(x>y)swap(x,y);
int pos=((long long)x*BASE+y)%mod;
for(auto p:a[pos])if(p.x==x&&p.y==y)return;
a[pos].push_back(Point(x,y,v));
}
int query(int x,int y) {
if(x>y)swap(x,y);
int pos=((long long)x*BASE+y)%mod;
for(auto p:a[pos])if(p.x==x&&p.y==y)return p.v;
return INT_MAX;
}
} Hash;
struct Edge {
int from,to,dist;
Edge(int x=0,int y=0,int v=0):from(x),to(y),dist(v) {}
bool operator < (const Edge& b) const {
return dist<b.dist;
}
};
int n,m,q,father[maxn],Time[maxn],Size[maxn],step=-1;
vector<Edge>edges,Edges;
vector<int>G[maxn];
void AddEdge(int x,int y) {
edges.push_back(Edge(x,y));
Size[x]++;
G[x].push_back(edges.size()-1);
Hash.insert(x,y,0);
}
int Get_Father(int x,int lim=INT_MAX) {
if(father[x]==x||Time[x]>lim)return x;
return Get_Father(father[x],lim);
}
int main() {
n=Get_Int();
m=Get_Int();
q=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int(),v=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
Edges.push_back(Edge(x,y,v));
}
Edges.push_back(Edge(0,0,0));
sort(Edges.begin(),Edges.end());
for(int i=1; i<=n; i++)father[i]=i;
for(auto e:Edges) {
step++;
if(step==0)continue;
int fx=Get_Father(e.from),fy=Get_Father(e.to);
if(fx==fy)continue;
if(Size[fx]<Size[fy])swap(fx,fy);
for(int id:G[fy]) {
Edge& e=edges[id];
int Next=e.to;
Hash.insert(fx,Next,step);
edges[id^1].to=fx;
}
G[fx].insert(G[fx].end(),G[fy].begin(),G[fy].end());
father[fy]=fx;
Size[fx]+=Size[fy];
Time[fy]=step;
}
for(int i=1; i<=q; i++) {
int x=Get_Int(),y=Get_Int(),Left=0,Right=m;
while(Left<=Right) {
int mid=(Left+Right)>>1;
int fx=Get_Father(x,mid),fy=Get_Father(y,mid);
if(fx==fy||Hash.query(fx,fy)<=mid)Right=mid-1;
else Left=mid+1;
}
if(Left==m+1)puts("-1");
else printf("%d\n",Edges[Left].dist);
}
return 0;
}
0%