【Luogu P1967】货车运输

Luogu P1967

题目大意：给定一张图和q个询问，询问x节点和y节点的路径之间最小边权最大可以是多少。

可以发现对于一条边\(E(x,y)\)，如果x到y有另一条路径且最小边权大于\(E(x,y)\)，那么这条边完全可以不考虑了。

综上所述，我们可以考虑对这张图使用Kruskal构建最大生成树。

那么两个点之间的路径就可以使用倍增LCA来求解了。

注意：原图可能并不连通，构成的可能是一个森林，所以要加入特判。

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxm=50005,maxn=10005;

struct data

{

	int sta,val,to,next;

	bool operator <(const data&x) const

	{

		return val>x.val;

	}

}e[2*maxm],edge[2*maxm];

int cnt,head[maxn],n,q,m,x,y,ans,z,fa[maxn],f[maxn][32],val[maxn][32],d[maxn],lg[maxn];

void add(int u,int v,int w)

{

	e[++cnt].sta=u;

	e[cnt].to=v;

	e[cnt].val=w;

}

int getf(int v)

{

	if (fa[v]!=v) return fa[v]=getf(fa[v]);

	return fa[v];

}

inline void merge(int x,int y)

{

	fa[getf(x)]=getf(y);

}

inline bool check(int x,int y)

{

	return fa[getf(x)]==fa[getf(y)];

}

void dfs(int now,int fat)

{

	f[now][0]=fat;d[now]=d[fat]+1;

	for (int i=1;i<=lg[d[now]];i++)

	{

		f[now][i]=f[f[now][i-1]][i-1];

		val[now][i]=min(val[now][i-1],val[f[now][i-1]][i-1]);

		//记录路径上的最小边权，注意理解。

	}

	for (int i=head[now];i;i=edge[i].next)

	{

		if (edge[i].to==fat) continue;

		val[edge[i].to][0]=edge[i].val;

		dfs(edge[i].to,now);

	}

}

int lca(int x,int y)

{

	if (!check(x,y)) return -1;

	if (d[x]<d[y]) swap(x,y);

	ans=2147483647;

	/*注意这里不能写ans=min(val[x][0],val[y][0]);这两条边不一定是必选的。

	因为y可能本身就是lca(x,y)*/

	while (d[x]>d[y])

	{

		ans=min(ans,val[x][lg[d[x]-d[y]]-1]);//注意顺序，更新x之前先更新最小边权。

		x=f[x][lg[d[x]-d[y]]-1];

	}

	if (x==y) return ans;

	for (int i=lg[d[x]]-1;i>=0;i--)

		if (f[x][i]!=f[y][i])

		{

			ans=min(ans,min(val[x][i],val[y][i]));

			x=f[x][i];y=f[y][i];

			//同样注意顺序

		}

	return ans=min(ans,min(val[x][0],val[y][0]));

}

int main()

{

	memset(val,0x3f,sizeof(val));

	scanf("%d%d",&n,&m);

	for (int i=1;i<=m;i++)

	{

		scanf("%d%d%d",&x,&y,&z);

		add(x,y,z);

		add(y,x,z);

	}

	for (int i=1;i<=n;i++) fa[i]=i;

	sort(e+1,e+1+cnt);

	int tmpcnt=cnt;

	cnt=0;

	for (int i=1;i<=tmpcnt;i++)

		if (!check(e[i].sta,e[i].to))

		{

			merge(e[i].sta,e[i].to);

			edge[++cnt].to=e[i].to;

			edge[cnt].val=e[i].val;

			edge[cnt].next=head[e[i].sta];

			head[e[i].sta]=cnt;

			edge[++cnt].to=e[i].sta;

			edge[cnt].val=e[i].val;

			edge[cnt].next=head[e[i].to];

			head[e[i].to]=cnt;

		}

	for (int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);

	for (int i=1;i<=n;i++)

		if (!d[i]) dfs(i,0);

	scanf("%d",&q);

	for (int i=1;i<=q;i++)

	{

		scanf("%d%d",&x,&y);

		printf("%d\n",lca(x,y));

	}

	return 0;

}

巴特西

【Luogu P1967】货车运输

最新文章

热门文章