J [NOIP2013]货车运输 lca 最大生成树 点和点之间所有路径最小值的最大值

标签：NOIP2013 min int 货车运输 点和点 re 000 dp dis

 链接：https://ac.nowcoder.com/acm/problem/16527
来源：牛客网

题目描述

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

输入描述:

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

接下来 m 行每行 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

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

输出

复制 3 -1 3

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 。

分析

题意：路径上的最小权值最大

容易想到floyd但是时间复杂度不够

只要用kruskal跑一边找出 n - 1条边的最大生成树，就能找到点和点之间所有路径的最大路径

然后用lca求一下每两个点之间的最小权值就可以了

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long int ll;
#define inf 0x3f3f3f3f
const int mod=1e9+7;
#define mst(a) memset(a,0,sizeof(a))
int d[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
const double eps = 1e-3;
const int N=1e5+7;
struct Edge{
    int next, w;
};

vector<Edge>edge[N];
ll dis[N][25];
int depth[N];
int dp[N][25];

struct node{
    int u,v,w;
}a[N];

class Dsu
{
public:
    int pre[N];
    
    Dsu(int n){
        for(int i=1; i<=n; i++){
            pre[i] = i;
        }
    }
    
    int find(int x){
        return x == pre[x] ? x : pre[x] = find(pre[x]);
    }
    
    void merge(int x, int y){
        int fx = find(x), fy = find(y);
        if(fx == fy){
            return;
        }
        pre[fx] = fy;
    }
};

class LCA
{
    bool vis[N];
public:
    void dfs(int u){
        for(int i=1; (1<<i) <= depth[u]; i++){
            dp[u][i] = dp[dp[u][i - 1]][i - 1];
            dis[u][i] = min(dis[u][i - 1], dis[dp[u][i - 1]][i - 1]);
        }
        vis[u] = true;
        for(auto it:edge[u]){
            if(vis[it.next]) continue;
            dis[it.next][0] = it.w;
            depth[it.next] = depth[u] + 1;
            dp[it.next][0] = u;
            dfs(it.next);
        }
    }
    
    LCA(int n){
        mst(vis);
        memset(dis,inf,sizeof(dis));
        for(int i = 1; i <= n; i++){
            if(!vis[i]){
                dp[i][0] = -1;
                depth[i] = 1;
                dfs(i);
            }
        }
    };
    
    ll getLCA(int x, int y){
        if(depth[x] < depth[y]) swap(x, y);
        ll re=inf;
        int t=depth[x] - depth[y];
        for(int i=0;t;i++,t>>=1){
            if(t & 1){
                re = min(re, dis[x][i]);
                x = dp[x][i];
            }
        }
        if(x == y) return re;
        for(int i = 20; i >= 0; i--){
            if(dp[x][i] != dp[y][i]){
                re = min(re, dis[x][i]);
                re = min(re, dis[y][i]);
                x = dp[x][i];
                y = dp[y][i];
            }
        }
        return min(re, min(dis[x][0], dis[y][0]));
    }
};

inline Dsu Kruskal(int n, int m){
    sort(a + 1, a + m + 1, 
         [](node x, node y)->bool{
             return x.w > y.w;
         });
    Dsu t(n);
    for(int i=1; i<=m; i++){
        int u = t.find(a[i].u), v = t.find(a[i].v);
        if(u != v){
            t.merge(u, v);
            edge[a[i].u].push_back({a[i].v,a[i].w});
            edge[a[i].v].push_back({a[i].u,a[i].w});
        }
    }
    return t;
}

int main()
{
    int n, m;
    scanf("%d%d",&n, &m);
    for(int i=1; i<=m; i++){
        scanf("%d%d%d", &a[i].u, &a[i].v, &a[i].w);
    }
    Dsu t = Kruskal(n,m);
    LCA lca(n);
    int q;
    scanf("%d",&q);
    while(q--){
        int x, y;
        scanf("%d%d",&x, &y);
        if(t.find(x) != t.find(y)){
            printf("-1\n");
        }else{
            printf("%lld\n",lca.getLCA(x, y));
        }
    }
    return 0;
}

 

标签：NOIP2013,min,int,货车运输,点和点,re,000,dp,dis
From： https://www.cnblogs.com/er007/p/16643857.html