NOIP2013 货车运输

题目：http://www.luogu.org/problem/show?pid=1967

分析：kruskal+LCA，注意LCA预处理的两个循环顺序别反了啊，卧槽在这个地方可是下了血本了！

代码：

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int Tmax=,Tmax2=,inf=;
struct Edge{
    int from,to,cost;
    bool operator <(const Edge &rhs)const
    {
        return cost>rhs.cost;
    }
};
Edge E[Tmax2];
vector <int> G[Tmax];
int n,m,f[Tmax],F[Tmax][],Fmin[Tmax][],Deep[Tmax];
bool v[Tmax];
int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}
void lca(int a,int b)
{
    if(find(a)!=find(b))
    {
        printf("-1\n");
        return;
    }
    int i,ans=inf,t;
    if(Deep[a]<Deep[b]) swap(a,b);
    t=Deep[a]-Deep[b];
    for(i=;i<=;i++)
        if(((<<i)&t)>){
            ans=min(ans,Fmin[a][i]);
            a=F[a][i];
        }
    for(i=;i>=;i--)
    {
        if(F[a][i]==F[b][i]) continue;
        ans=min(ans,Fmin[a][i]);
        ans=min(ans,Fmin[b][i]);
        a=F[a][i];
        b=F[b][i];
    }
    if(a==b) printf("%d\n",ans);
    else {
        ans=min(ans,Fmin[a][]);
        ans=min(ans,Fmin[b][]);
        printf("%d\n",ans);
    }
    return;
}
void dfs(int x)
{
    v[x]=true;
    int i,chid,len=G[x].size();
    for(i=;i<len;i++)
    {
        chid=E[G[x][i]].from==x?E[G[x][i]].to:E[G[x][i]].from;
        if(v[chid]==false){
            Deep[chid]=Deep[x]+;
            F[chid][]=x;
            Fmin[chid][]=E[G[x][i]].cost;
            dfs(chid);
        }
    }
    return;
}
void init()
{
    int i,j;
    for(i=;i<=n;i++)
      for(j=;j<=;j++)
        Fmin[i][j]=inf;
    for(i=;i<=n;i++)
      if(v[i]==false) dfs(i);
    for(j=;j<=;j++)
      for(i=;i<=n;i++)
      {
        if(F[F[i][j-]][j-]==) continue;
        F[i][j]=F[F[i][j-]][j-];
        Fmin[i][j]=min(Fmin[i][j-],Fmin[F[i][j-]][j-]);
      }
    return;
}
void kruskal()
{
    int i,tot=,fa,fb;
    sort(E+,E++m);
    for(i=;i<=n;i++) f[i]=i;
    for(i=;i<=m;i++)
    {
        if(tot==n-) break;
        fa=find(E[i].from);fb=find(E[i].to);
        if(fa==fb) continue;
        f[fa]=fb;
        tot++;
        G[E[i].from].push_back(i);
        G[E[i].to].push_back(i);
    }
    return;
}
int main()
{
    int i,q,a,b;
    scanf("%d %d",&n,&m);
    for(i=;i<=m;i++)
        scanf("%d %d %d",&E[i].from,&E[i].to,&E[i].cost);
    kruskal();
    init();
    scanf("%d",&q);
    for(i=;i<=q;i++)
    {
        scanf("%d %d",&a,&b);
        lca(a,b);
    }
    return ;
}