洛谷1967 货车运输(noip2013)

阅读全文大概需要 2分钟
本文总阅读量
Posted by yjjr's blog on February 6, 2018

标签:LCA,最大生成树,树上倍增

题目描述

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

输入输出格式

输入格式:

输入文件名为 truck.in。

输入文件第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道

路。 接下来 m 行每行 3 个整数 x、 y、 z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为z 的道路。注意: x 不等于y,两座城市之间可能有多条道路 

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

接下来 q 行,每行两个整数 x、y,之间用一个空格隔开,表示一辆货车需要从 x 城市运输货物到 y 城市,注意: x 不等于 y 

输出格式:

输出文件名为 truck.out。

输出共有 q 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。如果货

车不能到达目的地,输出-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%的数据,0 < n< 1,000,0 < m < 10,000,0 < q< 1,000;

对于 60%的数据,0 < n< 1,000,0 < m < 50,000,0 < q< 1,000;

对于 100%的数据,0 < n< 10,000,0 < m < 50,000,0 < q< 30,000,0 ≤ z ≤ 100,000。

 

这题是在济南时晚上和zmd拼手速AC的,刺激啊,30分钟拼手速&&RP去A题

分析:先最大生成树重构树,然后对于每个询问s->t,分别查询s->LCA(s,t) 和t->LCA(s,t)路径上的最小边权。可以用树上倍增的做法记录最小边权,类似于ST表吧

话说最近模拟赛写了不少最大生成树的题,日渐变成套路。。。

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
using namespace std;
inline ll read()
{
    ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxm=5e5+6,maxn=1e5+6,inf=0x3f3f3f;
struct edge{ll u,v,w;}e[maxm];
struct redge{ll to,next,w;}re[maxm];
int head[maxn],n,m,q,fastart[maxn],depth[maxn],fa[maxn][18],d[maxn][18],cnt=0;
bool vis[maxm]; 
inline bool cmp(edge x,edge y){return x.w>y.w;}
inline int find(int x){return x==fastart[x]?fastart[x]:fastart[x]=find(fastart[x]);}

void dfs(int x)
{
	vis[x]=1;
	rep(i,1,16){
	    if(depth[x]<(1<<i))break;
	    fa[x][i]=fa[fa[x][i-1]][i-1];
	    d[x][i]=min(d[x][i-1],d[fa[x][i-1]][i-1]);
	}
#define reg(x) for(int i=head[x];i;i=re[i].next)
	reg(x){
		if(vis[re[i].to])continue;
		fa[re[i].to][0]=x;
		d[re[i].to][0]=re[i].w;
		depth[re[i].to]=depth[x]+1;
		dfs(re[i].to);
	}
}

inline int lca(int x,int y)
{
	if(depth[x]<depth[y])swap(x,y);
	int t=depth[x]-depth[y];
	rep(i,0,16)if((1<<i)&t)x=fa[x][i];
	dep(i,16,0)
		if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}
	if(x==y)return x;
	return fa[x][0];
}

int ask(int x,int father)
{
	int re=inf,t=depth[x]-depth[father];
	rep(i,0,16)
		if((1<<i)&t){
			re=min(re,d[x][i]);
			x=fa[x][i];
		}
	return re;
}
int main()
{
	mem(d,inf);
    n=read(),m=read();
    rep(i,1,m)e[i].u=read(),e[i].v=read(),e[i].w=read();
    sort(e+1,e+1+m,cmp);
    rep(i,1,n)fastart[i]=i;
    rep(i,1,m){
    	int r1=find(e[i].u),r2=find(e[i].v);
    	if(r1!=r2){
		    fastart[r1]=r2; 
		    re[++cnt]=(redge){e[i].v,head[e[i].u],e[i].w};head[e[i].u]=cnt;
		    re[++cnt]=(redge){e[i].u,head[e[i].v],e[i].w};head[e[i].v]=cnt;
		}
		if(cnt==2*(n-1))break; 
	}
	rep(i,1,n)if(!vis[i])dfs(i);
	q=read();
	rep(i,1,q){
		int s=read(),t=read();
		int r1=find(s),r2=find(t);
		if(r1!=r2){printf("-1\n");continue;}
		else {int k=lca(s,t);printf("%lld\n",min(ask(s,k),ask(t,k)));}
	}
	return 0;
}
	



本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr