noip2013day1第三题 货车运输LCA+并查集

#代码是最为耐心、最能忍耐和最令人愉快的伙伴，在任何艰难困苦的时刻，它都不会抛弃你。#

今天每日一句好有趣啊。。感觉WA的代码只会一点点掏空我。。。

不说了，今天写一个LCA（最近公共祖先）就是关于一个跳跳跳的东西？？？

洛谷题面_(:зゝ∠)_ noip2013day1第三题 货车运输？？？（老司机【滑稽】？？）

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。 

所以是一道奇怪的题，首先是双向道路也就是无向图，addedge的时候要写两个。可以看到如果货车不能到达目的地的话就输出-1，所以可以骗分并查集来判断连通性。

所以LCA是啥？

LCA就是（Least Common Ancestors）最近公共祖先

比如像

比如图中21和15的LCA就是1

计算LCA分为5部分

1、把低的那个（就是深度较大）的那个跳到另一个点的深度（如果这一步完了重合也就是高的是LCA）

2、这一步21跳到13以后，两个分别跳到6和7也就是LCA下面一个的点（这里是两步）

3、最后跳一步合并维护（所以这里也是两步）

如果货车想运输尽可能多的东西，就要走限重尽可能大的路，所以说构成的树是最大生成树，先从大到小排序，然后预处理。然后用并查集来维护是否联通，如果不连通直接输出-1，然后用树上倍增求出答案，详见代码。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<climits>

using namespace std;

int n,m;

struct road

{

    int u,v,w;

}c[50010];

bool cmp(road x,road y)//存图 

{

    return x.w>y.w;

}

int p[10010];

int find(int x)//并查集 

{

    if(p[x]==0) return x;

    return p[x]=find(p[x]);

}

struct node //内存池 

{

    int v,w;

    int next;

}pool[30010];

int h[10010],cnt;

void addedge(int u,int v,int w) //建树 

{

    cnt++; pool[cnt].v=v; pool[cnt].w=w; pool[cnt].next=h[u]; h[u]=cnt;

    cnt++; pool[cnt].v=u; pool[cnt].w=w; pool[cnt].next=h[v]; h[v]=cnt;

}

int dep[10010],flag[10010],fa[10010][15],mx[10010][15];

void dfs(int u)// 预处理 

{

    flag[u]=1;

    int v;

    for(int i=h[u];i;i=pool[i].next)

        if(flag[v=pool[i].v]==0)

        {

            dep[v]=dep[u]+1;

            fa[v][0]=u;

            mx[v][0]=pool[i].w;

            for(int j=1;fa[v][j]=fa[fa [v][j-1] ][j-1];j++)

                mx[v][j]=min(mx[v][j-1],mx[ fa[v][j-1] ][j-1]);

            dfs(v);

        }

}

int lca(int u,int v) 

{

    if(dep[u]<dep[v]) swap(u,v);

    int ans=INT_MAX;

    for(int i=14;i>=0;i--)

        if(dep[fa[u][i]]>=dep[v])

        {

            ans=min(ans,mx[u][i]);

            u=fa[u][i];

        }

    if(u==v) return ans;

    for(int i=14;i>=0;i--)

        if(fa[u][i]!=fa[v][i])

        {

            ans=min(ans,mx[u][i]);

            ans=min(ans,mx[v][i]);

            u=fa[u][i];

            v=fa[v][i];

        }

    return min(ans,min(mx[u][0],mx[v][0]));

}

int q;

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++)

        scanf("%d%d%d",&c[i].u,&c[i].v,&c[i].w);

    sort(c+1,c+m+1,cmp);

    int u,v,w;

    for(int i=1;i<=m;i++)

        if(find(u=c[i].u)!=find(v=c[i].v))

        {

            addedge(u,v,c[i].w);

            p[find(u)]=find(v);

        }

    for(int i=1;i<=n;i++)

        if(flag[i]==0)

        {

            dep[i]=1;

            dfs(i);

        }

    scanf("%d",&q);

    for(int i=1;i<=q;i++)

    {

        scanf("%d%d",&u,&v);

        if(find(u)!=find(v)) printf("-1\n");

        else printf("%d\n",lca(u,v));

    }

    return 0;

}

好啦就这样。。