P1967 [NOIP 2013 提高组] 货车运输

题目背景

NOIP2013 提高组 D1T3

题目描述

A 国有 $n$ 座城市，编号从 $1$ 到 $n$，城市之间有 $m$ 条双向道路。每一条道路对车辆都有重量限制，简称限重。

现在有 $q$ 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入格式

第一行有两个用一个空格隔开的整数 $ n,m$，表示 A 国有 $ n$ 座城市和 $m$ 条道路。

接下来 $m$ 行每行三个整数 $x,y,z$，每两个整数之间用一个空格隔开，表示从 $x $ 号城市到 $ y $ 号城市有一条限重为 $z$ 的道路。
注意： $x\ne y$，两座城市之间可能有多条道路 。

接下来一行有一个整数 $q$，表示有 $q$ 辆货车需要运货。

接下来 $q$ 行，每行两个整数 $x,y$，之间用一个空格隔开，表示一辆货车需要从 $x$ 城市运输货物到 $y$ 城市，保证 $x\ne y$

输出格式

共有 $q$ 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。
如果货车不能到达目的地，输出 $-1$。

输入输出样例 #1

输入 #1

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

输出 #1

3
-1
3

说明/提示

对于 $30\%$ 的数据，$1\le n<1000$，$1\le m<10,000$，$1\le q<1000$；

对于 $60\%$ 的数据，$1\le n<1000$，$1\le m<5\times 10^4$，$1\le q<1000$；

对于 $100\%$ 的数据，$1\le n<10^4$，$1\le m<5\times 10^4$，$1 \le q< 3\times 10^4 $，$0\le z\le 10^5$。

算法思路

• 采用离线处理+并查集+启发式合并：
• 离线处理：先读入所有查询，再统一处理。
• 逆向 Kruskal 算法：按边权从大到小遍历边（类似最大生成树），逐步合并连通分量。
• 查询匹配：每个顶点维护一个集合，存储包含该点的未解决查询编号。当合并两个连通分量时，- - 检查公共查询编号，这些查询的答案即为当前边的权值。
• 启发式合并：将小集合合并到大集合，保证时间复杂度。

关键步骤

• 边排序：将边按权值从小到大排序（后续逆序遍历即从大到小）。
• 初始化：
• 并查集初始化：每个顶点自成一个集合。
• 为每个顶点创建查询集合：若查询 $i$ 包含顶点 $u$，则将 $i$ 加入 $u$ 的集合。
• 合并与匹配：
• 逆序遍历每条边 $(u,v,w)$：
• 找到 $u,v$ 所在集合的根 $f_u,f_v$。
• 若 $f_u\ne f_v$，则合并两集合（小集合并入大集合）。
• 遍历小集合中的查询编号：
• 若该编号也在大集合中，则当前边权 $w$ 即为答案（删除该编号避免重复计算）。
• 将剩余编号合并到大集合中。
• 输出结果：若查询未匹配到答案（两点不连通），输出 $-1$。

时间复杂度

• 排序边：$O(m\log m)$
• 并查集操作：$O(m\cdot \alpha (n))$
• 集合合并：$O(q\log q\log n)$（启发式合并）
• 总复杂度：$O(m\log m+q\log q\log n)$

核心逻辑说明

• 边权作用：当边 $(u,v,w)$ 合并两个连通分量时，$w$ 是当前连通分量的最小瓶颈值。
• 查询匹配：若查询 $i$ 的两个顶点分属被合并的两个分量，则 $w$ 是答案（因为 $w$ 是首次连通时的最大边权）。
• 集合维护：删除已解决的查询，避免后续无效匹配，提升效率。

详细代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+5;
set<int>a[N];
int n,m,q,ans[N],a1,b,fa[N];
struct node{
	int x,y,w;
	friend bool operator <(node aa,node bb)
	{
		return aa.w<bb.w;
	}
}h[N];
int find(int xx)
{
	if(fa[xx]==xx)return xx;
	return fa[xx]=find(fa[xx]);
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++)
		cin>>h[i].x>>h[i].y>>h[i].w;
	sort(h+1,h+1+m);
	cin>>q;
	for(int i=1;i<=q;i++)
	{
		cin>>a1>>b;
		a[a1].insert(i);
		a[b].insert(i);
	}
	for(int i=m;i>=1;i--)
	{
		int x=h[i].x;int y=h[i].y;int w=h[i].w;
		int fx=find(x);
		int fy=find(y);
		if(fx==fy)continue;
		if(a[fx].size()<a[fy].size())swap(fx,fy);
		queue<int>q1;
		for(set<int>::iterator it=a[fy].begin();it!=a[fy].end();it++)
		{
			if(a[fx].count(*it))
			{
				ans[*it]=w;
				q1.push(*it);
			}
			a[fx].insert(*it);
		}
		while(!q1.empty())
		{
			a[fx].erase(q1.front());
			q1.pop();
		}
		fa[fy]=fx;
	}
	for(int i=1;i<=q;i++)
		if(!ans[i])
			cout<<"-1"<<'\n';
	else
		cout<<ans[i]<<'\n';
	return 0;
}