NOIP201307货车运输

2016.1.28

试题描述

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。

输入示例

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

输出示例

3 -1 3

其他说明

数据范围：0<n<10,000，0<m<50,000，0<q<30,000，0≤z≤100,000。

先是最大生成树构图，注意构成的图可能不止一棵树，可能是好几棵树之间不联通。

然后对于询问，两个节点不联通（并查集判定）则无lca。

联通的话就LCA吧，因为路径肯定过lca，找lca的同时就把路径上的边权最小值更新了。

AC代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int maxlog=;
inline int read();
struct data
{
    int a,b,c;
    bool operator<(data d)const
    {
        return c>=d.c;
    }
}Edge[];
int n,m,q,father[],f[][],dist[][],dep[];
int last[],final[],to[],w[],e,vis[];
int FindFather(int x)
{
    if(x==father[x]) return x;
    return father[x]=FindFather(father[x]);
}
void AddEdge(int a,int b,int c)
{
    to[++e]=b;w[e]=c;last[e]=final[a];final[a]=e;
    to[++e]=a;w[e]=c;last[e]=final[b];final[b]=e;
}
void LCA(int x)
{
    vis[x]=;
    for(int i=;(<<i)<=dep[x];i++)
    {
        int c=f[x][i-];
        f[x][i]=f[c][i-];
        dist[x][i]=min(dist[x][i-],dist[c][i-]);
    }
    for(int i=final[x];i;i=last[i])
    {
        if(!vis[to[i]])
        {
            dep[to[i]]=dep[x]+;
            f[to[i]][]=x;
            dist[to[i]][]=w[i];
            LCA(to[i]);
        }
    }
}
int query(int a,int b)
{
    int ret=;
    if(dep[a]<dep[b]) swap(a,b);
    for(int i = maxlog ; i >=  ; i-- ) if(dep[a]-(<<i)>=dep[b])
    {
        ret=min(ret,dist[a][i]);a=f[a][i];
    }
    if(a==b) return ret;
    for(int i = maxlog ; i >=  ; i-- ) if(dep[a] > (<<i) && f[a][i] != f[b][i])
    {
        ret = min(ret, min(dist[a][i], dist[b][i]) );
        a=f[a][i];b=f[b][i];
    }
    return min(ret, min(dist[a][], dist[b][]) );
}
int main()
{
    n=read();m=read();
    for(int i=;i<=m;i++)
    {
        Edge[i].a=read();Edge[i].b=read();Edge[i].c=read();
    }
    sort(Edge+,Edge+m+);
    for(int i=;i<=n;i++) father[i]=i;
    for(int i=;i<=m;i++)
    {
        int u=FindFather(Edge[i].a),v=FindFather(Edge[i].b);
        if(u!=v)
        {
            father[u]=v;
            AddEdge(Edge[i].a,Edge[i].b,Edge[i].c);
        }
    }
    for(int i=;i<=n;i++) if(!vis[i]) LCA(i);
    q=read();
    while(q--)
    {
        int x=read(),y=read();
        if(FindFather(x) != FindFather(y)) printf("-1\n");
        else printf("%d\n",query(x,y));
    }
}
//----------------------------------------------------
inline int read()
{
    int x=,f=;char ch=getchar();
    while(ch<''||ch>'') {
        if(ch=='-') f=-;ch=getchar();
    }
    while(ch>=''&&ch<='')
    {
        x=x*+ch-'';
        ch=getchar();
    }
    return x*f;
}