[NOIP2013][LGOJ P1967]货车运输

Problem Link

题目描述

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

输入格式

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

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

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

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

输出格式

共有 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,0000<n<1,000,0<m<10,000,0<q<1,000；

对于 %60%的数据，0 < n < 1,000,0 < m < 50,000,0 < q< 1,0000<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,0000<n<10,000,0<m<50,000,0<q<30,000,0≤z≤100,000。

最大生成树 + LCA

#include<bits/stdc++.h>

using namespace std;

const int maxm = 50000 + 5;

const int maxn = 10000 + 5;

const int inf = 1e9 - 1; // 坑点， 坑了我2h

int n, m, q;

int fa[maxn];

int find(int x){

	if(x == fa[x])

		return x;

	else

		return fa[x] = find(fa[x]);

}

//如果两个点不在一个联通块（点集<并查集>）中，则输出-1

struct G{

	int x, y, z;

	bool operator < (const G & nxt){

		return z > nxt.z;

	}

}g[maxm];

//保存初始图

struct E{

	int to, z;

};

vector <E> e[maxn];

//保存最大生成树的图<贪心思想>

void kruscal(){

	sort(g + 1, g + 1 + m);

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

		fa[i] = i;

	}

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

		int x = find(g[i].x);

		int y = find(g[i].y);

		int z = g[i].z;

		if(x == y)

			continue;

		fa[x] = y;

		e[g[i].x].push_back(E{g[i].y, z});

		e[g[i].y].push_back(E{g[i].x, z});

	}

}

//kruscal最大生成树&建图

bool vis[maxn];

int f[maxn][21];//f[i,j] : i的2^j辈祖先

int w[maxn][21];//w[i,j] : i到f[i,j]的路径上最短的一条边（限制了货车的限重）

int dep[maxn];

void dfs(int x){

	vis[x] = 1;

	for(int i = 0;i < e[x].size();i ++){

		int y = e[x][i].to, z = e[x][i].z;

		if(vis[y])continue;

		dep[y] = dep[x] + 1;

		f[y][0] = x;

		w[y][0]	= z;//子（y）父（x）之间距离为当前边权

		dfs(y);

	}

}

//lca预处理

int lca(int x, int y){

	if(find(x) != find(y)){

		return -1;

	}

	if(dep[x] < dep[y])

		swap(x, y);

	int ans = inf;//先置infinite

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

		if(dep[f[x][i]] >= dep[y]){

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

			//这里是x到与y同一高度的祖先的路径上的最小值

			x = f[x][i];

		}

	}

	if(x == y)

		return ans;

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

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

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

			//这里是两条路径(x -> f[x][i], y -> f[y][i])上的最小边权

			x = f[x][i];

			y = f[y][i];

		}

	}

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

	//还有到真正的lca的两条边的最小值

	return ans;

}//注意： 这里的lca返回的是 path: x -> lca(x, y) & lca(x, y) -> y 的路径上的最小边权, 即货车限重

int main(){

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

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

		scanf("%d%d%d", &g[i].x, &g[i].y, &g[i].z);

	}

	kruscal();

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

		if(!vis[i]){

			dep[i] = 1;

			dfs(i);

			f[i][0] = i;

			w[i][0] = inf;

		}

	}

	//预处理

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

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

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

			w[j][i] = min(w[j][i - 1], w[f[j][i - 1]][i - 1]);

		}

	}

	//预处理

	scanf("%d", &q);

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

		int x, y;

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

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

	}

	return 0;

}

巴特西