P1967 货车运输[生成树+LCA]

题目描述

A国有n座城市，编号从 1到n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q* 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

解析

看我蒻到把双向边连成单向边debug了一上午。

很显然，如果只有一个询问，我们贪心地连边直到起点和终点连通即可。如果有这么多个询问，我们仍然可以像最小生成树那样如法炮制，贪心地搞一个“最大生成树”出来（我也不知道有没有），然后你甚至可以树剖。然后我们就在树上乱搞，随便用一种算法求出树上任意两点之间路径的最小权值就行了。

这里我用到了树上倍增求LCA，分别统计两个点到它们LCA的最小权值，对这两个值再取min就是最终答案。

参考代码

#include<cstdio>

#include<iostream>

#include<cmath>

#include<cstring>

#include<ctime>

#include<cstdlib>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#define N 500010

#define INF 0x7fffffff

#define IN freopen("data.in","r",stdin);

using namespace std;

inline int read()

{

	int f=1,x=0;char c=getchar();

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

	return x*f;

}

struct node{

	int from,to,edge;

}a[N];

struct rec{

	int next,ver,edge;

}g[N];

int head[N],tot;

int fa[N],f[30][N],w[30][N],d[N],n,m;//f[i][x]表示x节点的2^i辈父亲，w[i][x]表示x节点到其2^i辈父亲的最小权值，d[x]表示节点x的深度

queue<int> q;

inline void add(int x,int y,int val)

{

	g[++tot].ver=y,g[tot].edge=val;

	g[tot].next=head[x],head[x]=tot;

}

inline int get(int x)

{

	return fa[x]==x?x:fa[x]=get(fa[x]);

}

inline void merge(int x,int y)

{

	x=get(x),y=get(y);

	if(x!=y) fa[x]=y;

}

inline void init(int x)//BFS预处理f[][],w[][]

{

	q.push(x);d[x]=1;

	while(q.size()){

		int index=q.front();q.pop();

		for(int i=head[index];i;i=g[i].next){

			int y=g[i].ver,z=g[i].edge;

			if(d[y]) continue;

			f[0][y]=index;w[0][y]=z;

			d[y]=d[index]+1;

			for(int j=1;j<25;++j){

				f[j][y]=f[j-1][f[j-1][y]];

				w[j][y]=min(w[j-1][y],w[j-1][f[j-1][y]]);//仿照ST表求法预处理w数组

			}

		q.push(y);

		}

	}

}

inline int calc(int x,int y)//倍增求LCA

{

	int ans=INF;

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

	for(int i=24;i>=0;--i)

		if(d[f[i][y]]>=d[x]) ans=min(ans,w[i][y]),y=f[i][y];

	if(x==y) return ans;

	for(int i=24;i>=0;--i){

		if(f[i][y]==f[i][x]) continue;

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

	}

	if(x==y) return ans;

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

	return ans;

}

bool cmp(node a,node b){return a.edge>b.edge;}

int main()

{

	//IN

	int q;

	n=read(),m=read();

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

		a[i].from=read(),a[i].to=read(),a[i].edge=read();

	sort(a+1,a+m+1,cmp);//最大生成树，并查集实现

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

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

		int x=get(a[i].from),y=get(a[i].to);

		if(x==y) continue;

		merge(x,y),add(a[i].from,a[i].to,a[i].edge),add(a[i].to,a[i].from,a[i].edge);

	}

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

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

		if(!d[i]) init(i);//可能出现森林

	q=read();

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

		int u,v;

		u=read(),v=read();

		int x=get(u),y=get(v);

		if(x!=y){

			printf("-1\n");continue;//如果两个点不在一棵树上，无解

		}

		printf("%d\n",calc(u,v));

	}

	return 0;

}

巴特西

P1967 货车运输[生成树+LCA]

题目描述

解析

参考代码

最新文章

热门文章