【做题记录】[NOIP2013 提高组] 货车运输

Problem

[NOIP2013 提高组] 货车运输

题目大意：

给定一个 \(n\) 个点 \(m\) 条边的无向图，不保证连通，边有权值。有 \(q\) 次询问，每次询问从 \(u\) 到 \(v\) 的路径中边权最小的边的最大值。

Solution

首先，观察题目，可以满足条件的路径一定在整个图的最大生成树上。
更准确的说，是在整个图的“最大瓶颈生成树”上，也就是这个生成树上最小的边最大。
显然这是正确的，可以从它的定义上来理解。

那么我们首先求出图的“最大瓶颈生成树”。由于这是一棵树，所以两点之间的路径是唯一的，求出这条路径的最小的边权即可。

对于处理边权，我们可以使用树剖。
常用的方法是在第一遍预处理之后枚举所有的边，将边权放到深度较低的点上。
但是此时，在处理链上信息时，两点的 LCA 上的信息是不该被记录的。
原来的代码应该长这个亚子：

int query_path(int x,int y)
{
	int res=1e9;
	while(top[x]!=top[y])
	{
		if(depth[top[x]]depth[y]) swap(x,y);
	res=min(res,query(id[x],id[y]));
	return res;
}

在最后的数据更新，即res=min(res,query(id[x],id[y]));中，\(x=LCA(x,y)\)，所以此时只要把这句话改成res=min(res,query(id[x]+1,id[y]));即可。

然后还有一个问题就是，图是不连通的，所以预处理 dfs 的时候要注意对每个树都处理一下。然后用并查集维护连通性就行了。

另外，因为是静态查询（边权不变），所以可以用 ST 表来维护。

还有一个注意点放代码里了。

Code

#include
#include
#include
#define MAXN 10005
#define MAXM 50005
using namespace std;

int n,m,q;
struct node{int u,v,w;}a[MAXM];
bool cmp(node x,node y){return x.w>y.w;}
struct bin
{
	int f[MAXN];
	bin()
	{
		for(int i=0;isize[son[now]]) son[now]=g.to[i];
		}
	return ;
}//树剖第一遍预处理
void dfs2(int now,int F)
{
	top[now]=F;
	id[now]=++cnt;
	Min[id[now]][0]=w[now];
	if(!son[now]) return ;
	dfs2(son[now],F);
	for(int i=g.hd[now];i;i=g.nxt[i])
		if(g.to[i]!=fa[now]&&g.to[i]!=son[now]) dfs2(g.to[i],g.to[i]);
	return ;
}//树剖第二遍预处理
int query(int l,int r)
{
	if(l>r) return 1e9;//这里这里，这句话一定要加！
    //虽然我也不知道为什么QwQ
	int k=lg[r-l+1];
	return min(Min[l][k],Min[r-(1<depth[y]) swap(x,y);
	res=min(res,query(id[x]+1,id[y]));
	return res;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++)
		if(!b.query(a[i].u,a[i].v))
		{
			b.add(a[i].u,a[i].v);
			g.add(a[i].u,a[i].v,a[i].w);
			g.add(a[i].v,a[i].u,a[i].w);
		}
    //Kruskal 求出“最大瓶颈生成树”
	for(int i=1;i<=n;i++)
		if(!size[i]) dfs1(i,0);
    //第一遍预处理
	for(int i=1;i<=n;i++)
		for(int j=g.hd[i];j;j=g.nxt[j])
			if(depth[i]>depth[g.to[j]]) w[i]=g.dt[j];
			else w[g.to[j]]=g.dt[j];
    //把边权放到深度较大的点上
	for(int i=1;i<=n;i++)
		if(!id[i]) dfs2(i,i);
    //第二遍预处理
	lg[0]=-1;
	for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
    //预处理出log
	for(int k=1;(1<