「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]$用数组开不下，但实际总状态量很小，使用map或hash来优化空间。
时间复杂度$O(n\log^2 n)$或$O(n\log n)$。

---

代码

#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;
}