题解 洛谷P1967货车运输

说到1967,这是一个神奇的日子…

在公元1967年,在圆谷株式会社诞生了一个神作----ultra seven!!!

对于seven的知名度,L_Y_T略略的计算了一下: a n s = ( ∑ i = 1 n n − 初 代 年 份 n ∗ 1 n ) × 100 ans = (\sum_{i=1}^{n}\frac{n-初代年份}{n}*\dfrac{1}{n})\times100 ans=(∑i=1n​nn−初代年份​∗n1​)×100%

其中 n 是 当前剧上映的时间

他的op十分的好听,seven的名字响彻云霄!!! ------by L_Y_T

哎呀,扯远了

直接上题目描述吧…

输入格式
输入文件第一行有两个用一个空格隔开的整数 nnn，mmm，表示 A 国有 nnn 座城市和 mmm 条道路。

接下来 mmm 行每行 333 个整数 xxx、yyy、zzz，每两个整数之间用一个空格隔开，表示从 xxx 号城市到 yyy 号城市有一条限重为 zzz 的道路。注意：xxx 不等于 yyy，两座城市之间可能有多条道路。

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

接下来 qqq 行，每行两个整数 xxx、yyy，之间用一个空格隔开，表示一辆货车需要从 xxx 城市运输货物到 yyy 城市，注意：xxx 不等于 yyy。
输出格式
输出共有 qqq 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出 −1-1−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<10000 < n < 1,0000<n<1000，0<m<100000 < m < 10,0000<m<10000，0<q<10000 < q < 1,0000<q<1000；

对于 60% 的数据，0<n<10000 < n < 1,0000<n<1000，0<m<500000 < m < 50,0000<m<50000，0<q<10000 < q < 1,0000<q<1000；

对于 100% 的数据，0<n<100000 < n < 10,0000<n<10000，0<m<500000 < m < 50,0000<m<50000，0<q<300000 < q < 30,0000<q<30000，0≤z≤1000000 \leq z \leq 100,0000≤z≤100000。

关于题面一片混乱,这全都是L_Y_T懒癌晚期的结果

好了,不多说一些,直接上代码

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define maxn 200010 
using namespace std ;
int read(){
	int x = 0 ;int f = 1 ; char s = getchar() ;
	while(s>'9' || s<'0') {if(s=='-')f=-1 ; s=getchar();}
	while(s<='9'&&s>='0') {x=x*10+(s-'0');s=getchar();}
	return x*f ;
}int n , m ;
struct Edge1{
	int x , y , z ;
}a1[maxn];
struct Edge2{
	int x , y , z , next ;
}a2[maxn] ;
int t , head[maxn] , dep[maxn] , f[maxn] , fa[maxn][30] , w[maxn][30] ;
int find(int x) {
	if(f[x] != x) f[x] = find(f[x]) ;
	return f[x] ; 
}
int vis[maxn] ;
void add(int x , int y , int z) {
	a2[++t].x = x ;
	a2[t].y = y ;
	a2[t].z = z ;
	a2[t].next = head[x] ;
	head[x] = t ;
}
void unionn(int x , int y) {x = find(x) ; y = find(y);f[x]=y;}
int cmp (Edge1 x , Edge1 y){return x.z > y.z ;}
void kruskal(){
	sort(a1+1,a1+1+m,cmp) ;
	//cout << "-" <<endl ;
	for(int i = 1 ; i <= n ; i ++) 
	f[i] = i ;
	for(int i = 1 ; i <= m ; i ++) 
		if(find(a1[i].x) != find(a1[i].y)) {
			unionn(a1[i].x,a1[i].y) ;
			add(a1[i].x,a1[i].y,a1[i].z) ;
			add(a1[i].y,a1[i].x,a1[i].z) ;
		}
	return ;
}
int q ;
int lca(int x , int y ) { 
	if(find(x) != find(y)) return -1;
	int ans = 0x7ffffff ;
	if(dep[x] > dep[y]) swap(x,y) ;
	for(int i = 20 ; i >= 0 ; i--) {
		if(dep[fa[y][i]] >= dep[x]) {
			ans = min(ans,w[y][i]) ;
			y = fa[y][i] ;
		}
	}
	if(x == y ) return ans ;
	for(int i = 20 ; i >= 0 ; i--) {
		if(fa[x][i] != fa[y][i]) {
			ans=min(ans, min(w[x][i], w[y][i]));
			x = fa[x][i] ;
			y = fa[y][i] ;
		}
	}
	ans=min(ans, min(w[x][0], w[y][0]));
	return ans ;
}
void dfs(int node)
{
    vis[node]=true;
    for(int i=head[node]; i; i=a2[i].next){ 
        int v=a2[i].y;
        if(vis[v]) continue;
        dep[v]=dep[node]+1; 
        fa[v][0]=node; 
        w[v][0]=a2[i].z;
        dfs(v);
    }
    return ;
}
int main(){
	n = read() , m = read() ;
		//cout << " * " <<endl ;
	for(int i = 1 ; i <= m ; i ++) {
// cout << " * " <<endl ;
		int x , y , z ;
		x = read() , y = read() , z = read() ;
		a1[i].x = x ;
		a1[i].y = y ;
		a1[i].z = z ;
	}
	kruskal() ;
	for(int i = 1 ; i <= n ; i ++) {
		//cout << "+" <<endl ; 
		if(!vis[i]) {
			dep[i] = 1 ;
			dfs(i) ;
			fa[i][0] = i ;
			w[i][0] = 0x7ffffff ;
		}
	}
	//dfs(i) ;
	for(int i = 1 ; i <= 20 ; i ++) 
		for(int j = 1 ; j <= n ; j ++){
			//cout << "* " <<endl ;
			fa[j][i] = fa[fa[j][i-1]][i-1] ;
			w[j][i] = min(w[j][i-1],w[fa[j][i-1]][i-1]) ;
		}
	q = read() ;
	for(int i = 1 ; i <= q ; i ++) {
		int x , y ;
		x = read() , y = read() ;
		cout << lca(x,y) <<endl ; 
  	}
 	return 0;
}

完结散花!!!