【算法分析】之从次小生成树看LCA

额。第一使用MD，好紧张。
好吧，原来我还是个水货啊。。
最小生成树我们都知道该怎么求吧

把边按照权值大小排序，然后从小到大依次选择这些边，但是选择这些边有一个条件：不能构成环，当然这一点可以用并查集来实现

但是我们怎么求最小生成树？
首先这么看。假设图为G(V,E) |V|=n |E|=m
先求出一个最小生成树，它的边集合为E’
我们首先可以得到一个直观的想法。

每次只删除最小生成树中的一条边，然后重新跑最小生成树，得出答案这些最小生成树中最小的即为次小生成树的值

这样的话复杂度为O(n*n*logn)
然后我们考虑次小生成树边集为E’’
显然|E’‘∩E’|=n-2，和最小生成树只有一条边不同
这条边一定位于E-E’，那么我们可以试着考虑
假设e(a,b)属于E-E’这个集合，在最小生成树中

加入一条边e(a,b)一定会构成环，构成环之后我们需要删除一条边使得它变成另一颗生成树，但是要求这颗树一定是最小生成树

那么现在考虑

我们应该删除哪条边？

在一颗树中，任意两点之间的路径是唯一的

我们应该删除的边一定位于a到b的最短路径上，并且那条边的边权是最大的

为什么？因为只有删除a到b的最短路径上的某条边之后才不会构成环。
简单来说就是：
我们需要知道

树上任意两点间最短路径上的最大边权

好了，问题转换成这个了，现在我们怎么求树上任意两点间的最短路径上的最大边权？
我们可以得到一个朴素的算法，直接找其最短路，记录路径上最大边权。
但是这样复杂度为(n^2)
当n太大就无能为力了。我们需要一个比较高效的算法。
好了现在可以引入LCA了，汗(⊙﹏⊙)b。。。。。
LCA是什么？

最近公共祖先

特指的是对于树上的任意两点(a,b)，求离它们最近的那个节点c。节点c就是(a,b)的最近公共祖先。
当然求LCA的算法有很多，比如tarjan的离线算法O(n+q)，RMQ±1，倍增法
由于倍增法比较方便O(n+n*logn)，所以可以考虑使用倍增LCA。
倍增LCA做法其实核心就是st(也就是RMQ)了。
定义一个数组p[i][j]代表的是从i节点往上的第2^j个节点是多少
这样可以得到一个递推方程式
i往上走2^(j-1)再走2(j-1)刚好是往上走的第2^j个节点
p[i][j]=p[p[i][j-1]][j-1]
同理可以顺便维护i往上走的第2^j个节点边权的最大值
这样当我们要求a到b路径上边权最大值可以求出a到c和b到c的最大值就是了

复杂度为O(m*logm)

题目链接：http://poj.org/problem?id=1679
代码

//author: CHC
//First Edit Time:	2015-04-05 10:02
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+4;
const int MAXM=1e+5;
const int MAXX=15;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
struct Edge {
    int to,next,w,id;
    int select;
    Edge(){}
    Edge(int _to,int _next,int _w,int _id):to(_to),next(_next),w(_w),id(_id){select=0;}
}e[MAXM];
bool cmp(const Edge &x,const Edge &y){
    if(x.w!=y.w)return x.w<y.w;
    return x.id<y.id;
}
int p[MAXN][MAXX],mm[MAXN][MAXX],deep[MAXN],head[MAXN],tot=0;
int n,m;
void init(){
    memset(head,-1,sizeof(head));
    memset(deep,0,sizeof(deep));
    memset(mm,0,sizeof(mm));
    tot=0;
}
void AddEdge(int u,int v,int w){
    e[tot]=Edge(v,head[u],w,tot);
    head[u]=tot++;
    e[tot]=Edge(u,head[v],w,tot);
    head[v]=tot++;
}
void dfs(int u){
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(!deep[v]&&e[i].select){
            p[v][0]=u;
            deep[v]=deep[u]+1;
            mm[v][0]=e[i].w;
            dfs(v);
        }
    }
}
void st(){
    for(int j=1;(1<<j)<=n;j++)
    for(int i=1;i<=n;i++)
        if(p[i][j-1]!=-1){
            p[i][j]=p[p[i][j-1]][j-1];
            mm[i][j]=max(mm[i][j-1],mm[p[i][j-1]][j-1]);
        }
        //else p[i][j]=-1;
}
int mst_lca(int a,int b){
    if(deep[a]<deep[b])swap(a,b);
    int x=deep[a]-deep[b],y=0,maxm=0;
    //printf("%d %d x:%d\n",a,b,x);
    //printf("tx:%d %d\n",deep[a],deep[b]);
    while(x){
        if(x&1){
            maxm=max(maxm,mm[a][y]);
            a=p[a][y];
            //printf("y:%d h1:%d %d\n",y,a,mm[a][y]);
        }
        x>>=1;
        ++y;
    }
    //printf("maxm:%d\n",maxm);
    if(a==b)return maxm;
    for(x=1;(1<<x)<=deep[a];x++);
    while(--x>=0){
        if(p[a][x]!=-1&&p[a][x]!=p[b][x]){
            maxm=max(maxm,mm[a][x]);
            a=p[a][x];
            maxm=max(maxm,mm[b][x]);
            b=p[b][x];
        }
    }
    maxm=max(mm[a][0],max(maxm,mm[b][0]));
    return maxm;
}
int path[MAXN];
int Find(int x){
    return x==path[x]?x:path[x]=Find(path[x]);
}
int Union(int x,int y){
    x=Find(x);y=Find(y);
    if(x==y)return false;
    path[x]=y;
    return true;
}
int read(){
    char ch;
    while(!((ch=getchar())>='0'&&ch<='9'));
    int t=ch-'0';
    while((ch=getchar())>='0'&&ch<='9'){
        t=(t<<1)+(t<<3)+ch-'0';
    }
    return t;
}
int main()
{
    int t;
    //scanf("%d",&t);
    t=read();
    while(t--){
        //scanf("%d%d",&n,&m);
        n=read();m=read();
        init();
        for(int i=0;i<=n;i++)path[i]=i;
        for(int i=0,x,y,w;i<m;i++){
            //scanf("%d%d%d",&x,&y,&w);
            x=read();y=read();w=read();
            AddEdge(x,y,w);
        }
        int ans=0;
        sort(e,e+tot,cmp);
        for(int i=0;i<tot;i+=2){
            if(Union(e[i].to,e[i^1].to)){
                ans+=e[i].w;
                e[i].select=e[i^1].select=1;
                //printf("ans:%d\n",ans);
            }
        }
        p[1][0]=-1;
        deep[1]=1;
        dfs(1);
        st();
        int ans1=INF;
        for(int i=0;i<tot;i+=2){
            if(!e[i].select){
                ans1=min(ans1,ans-mst_lca(e[i].to,e[i^1].to)+e[i].w);
                //printf("%d %d %d %d\n",e[i].to,e[i^1].to,mst_lca(e[i].to,e[i^1].to),e[i].w);
                //printf("ans1:%d\n",ans1);
            }
        }
        //printf("%d %d\n",ans1,ans);
        if(ans1==ans)puts("Not Unique!");
        else printf("%d\n",ans);
    }
    return 0;
}

如有错误或者不合理的地方请指正