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;

}

好啦就這樣。。