JDOJ-2228:[NOIP2013]货车运输 D1 T3

Description

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

给出了一个无向图，问任意两点间路径上边权最小值最大的路径的最小边权。
kruskal+倍增
首先，想到只需要用尽量边权大的边将图联通就好了，所以kruskal求最大生成树。搜索处理一个森林中每一个点所属的树，该点的fa，与fa连的边的边权。最后倍增，将节点到2ⁿ级祖先边的边权最小值弄出来。查询时先判断所属的树，求LCA，两节点和LCA之间的最小边权倍增得出。
注意：如果LCA和一个节点重合，这个节点的最小边权需清成极大值。然后倍增维护时需要再找一下节点的len-2ⁿ级祖先（卡了好长时间）。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define M 51000
#define N 11000
int n,m,id,mx,t,c,k,dx,dy,q,ans1,ans2,num;
int v[N];
struct node
{
    int v1,v2,date;
}a[M];
int f[N][20],dis[N][20],fa[N],deep[N],bin[50],Log[N];
int to[N<<1],head[N],nxt[N<<1],data[N<<1],cnt;
void add(int x,int y,int z)
{
    to[++cnt]=y;
    nxt[cnt]=head[x];
    data[cnt]=z;
    head[x]=cnt;
}
int find(int x)
{
    return x==fa[x] ? x:fa[x]=find(fa[x]);
}
bool cmp(node x,node y)
{
    return x.date>y.date;
}
void dfs(int x,int pre)
{
    int i,y;
    for(i=head[x];i;i=nxt[i])
    {
        y=to[i];
        if(y==pre) continue;
        v[y]=id;deep[y]=deep[x]+1;
        f[y][0]=x;dis[y][0]=data[i];
        dfs(y,x);
    }
}
void getbin()
{
    bin[0]=1;
    for(int i=1;i<=mx;i++)
        bin[i]=bin[i-1]<<1;
}
int lca(int x,int y)
{
    if(deep[x]<deep[y]) swap(x,y);
    int i,tmp=deep[x]-deep[y];
    for(i=0;bin[i]<=tmp;i++)
        if(tmp&bin[i]) x=f[x][i];
    if(x==y) return x;
    for(i=mx;i>=0;i--)
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
int ances(int x,int step)
{
    int i;
    for(i=0;bin[i]<=step;i++)
        if(step&bin[i]) x=f[x][i];
    return x;
}
int main()
{
    scanf("%d%d",&n,&m);
    int i,j;
    for(i=1;i<=n;i++) fa[i]=i;
    memset(dis,0x3f,sizeof(dis));
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&a[i].v1,&a[i].v2,&a[i].date);
    sort(a+1,a+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        dx=find(a[i].v1);
        dy=find(a[i].v2);
        if(dx!=dy)
        {
            num++;
            fa[dx]=dy;
            add(a[i].v1,a[i].v2,a[i].date);
            add(a[i].v2,a[i].v1,a[i].date);
            if(num==n-1)break;
        }
    }
    for(i=1;i<=n;i++)
        if(!v[i])
        {
            id++;v[i]=id;
            dfs(i,0);
        }
    for(i=2;i<=n;i++)
        Log[i]=Log[i>>1]+1;
    mx=Log[n];
    getbin();
    for(i=1;i<=mx;i++)
        for(j=1;j<=n;j++)
        {
            if(bin[i]<=deep[j])
            {
                f[j][i]=f[f[j][i-1]][i-1];
                dis[j][i]=min(dis[f[j][i-1]][i-1],dis[j][i-1]);
            }
        }
    scanf("%d",&q);
    int x,y,tmp;
    while(q--)
    {
        scanf("%d%d",&x,&y);
        if(v[x]!=v[y])
        {
            printf("-1\n");
            continue;
        }
        t=lca(x,y);
        c=deep[x]-deep[t];
        //printf("dis%d\n",c);
        if(c!=0)
        {
            k=Log[c];
            tmp=ances(x,c-bin[k]);
            //printf("anc%d\n",tmp);
            ans1=min(dis[x][k],dis[tmp][k]);
        }
        else ans1=1<<30;
        c=deep[y]-deep[t];
        //printf("dis%d\n",c);
        if(c!=0)
        {
            k=Log[c];
            tmp=ances(y,c-bin[k]);
            //printf("anc%d\n",tmp);
            ans2=min(dis[y][k],dis[tmp][k]);
        }
        else ans2=1<<30;
        printf("%d\n",min(ans1,ans2));
    }
    return 0;
}