POJ 1679 The Unique MST：次小生成树【倍增】

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

题意：

　　给你一个图，问你这个图的最小生成树是否唯一。

题解：

　　求这个图的最小生成树和次小生成树。如果相等，则说明不唯一。

　　次小生成树（倍增算法）：

　　　　maxn[k][i]：表示从节点i向上走2^k步，这一段中边权的最大值。

　　　　枚举每一条不在MST中的边，求出这条边两端点之间在MST上路径上的最大边权mx。

　　　　次小生成树（非严格） = max(MST - mx + len)

AC Code:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define MAX_N 105
#define MAX_E 10005
#define MAX_K 20
#define INF 1000000000

using namespace std;

struct E
{
    int s;
    int t;
    int len;
    E(int _s,int _t,int _len)
    {
        s=_s;
        t=_t;
        len=_len;
    }
    E(){}
    friend bool operator < (const E &a,const E &b)
    {
        return a.len<b.len;
    }
};

struct Edge
{
    int dest;
    int len;
    Edge(int _dest,int _len)
    {
        dest=_dest;
        len=_len;
    }
    Edge(){}
};

int n,m,t;
int fa[MAX_N];
int dep[MAX_N];
int par[MAX_K][MAX_N];
int maxn[MAX_K][MAX_N];
bool vis[MAX_E];
vector<E> e;
vector<Edge> edge[MAX_N];

void read()
{
    cin>>n>>m;
    e.clear();
    for(int i=1;i<=n;i++)
    {
        edge[i].clear();
    }
    int a,b,v;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b>>v;
        e.push_back(E(a,b,v));
    }
}

void init_union_find()
{
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
}

int find(int x)
{
    return fa[x]==x ? x : fa[x]=find(fa[x]);
}

void unite(int x,int y)
{
    int px=find(x);
    int py=find(y);
    if(px==py) return;
    fa[px]=py;
}

bool same(int x,int y)
{
    return find(x)==find(y);
}

int kruskal()
{
    init_union_find();
    sort(e.begin(),e.end());
    memset(vis,false,sizeof(vis));
    int cnt=0;
    int res=0;
    for(int i=0;i<e.size() && cnt<n-1;i++)
    {
        E temp=e[i];
        if(!same(temp.s,temp.t))
        {
            cnt++;
            res+=temp.len;
            vis[i]=true;
            unite(temp.s,temp.t);
            edge[temp.s].push_back(Edge(temp.t,temp.len));
            edge[temp.t].push_back(Edge(temp.s,temp.len));
        }
    }
    return cnt==n-1 ? res : -1;
}

void dfs(int now,int p,int d,int l)
{
    dep[now]=d;
    par[0][now]=p;
    maxn[0][now]=l;
    for(int i=0;i<edge[now].size();i++)
    {
        Edge temp=edge[now][i];
        if(temp.dest!=p) dfs(temp.dest,now,d+1,temp.len);
    }
}

void init_lca()
{
    dfs(1,-1,0,-1);
    for(int k=0;k+1<MAX_K;k++)
    {
        for(int i=1;i<=n;i++)
        {
            if(par[k][i]==-1)
            {
                par[k+1][i]=-1;
                maxn[k+1][i]=-1;
            }
            else
            {
                par[k+1][i]=par[k][par[k][i]];
                maxn[k+1][i]=max(maxn[k][i],maxn[k][par[k][i]]);
            }
        }
    }
}

int cal_max(int a,int b)
{
    if(dep[a]>dep[b]) swap(a,b);
    int res=-1;
    for(int k=0;k<=MAX_K && dep[a]!=dep[b];k++)
    {
        if(((dep[b]-dep[a])>>k)&1)
        {
            res=max(res,maxn[k][b]);
            b=par[k][b];
        }
    }
    if(a==b) return res;
    for(int k=MAX_K-1;k>=0;k--)
    {
        if(par[k][a]!=par[k][b])
        {
            res=max(res,maxn[k][a]);
            res=max(res,maxn[k][b]);
            a=par[k][a];
            b=par[k][b];
        }
    }
    return max(res,maxn[0][a]);
}

int sst(int mst)
{
    if(mst==-1) return -1;
    init_lca();
    int ans=INF;
    for(int i=0;i<e.size();i++)
    {
        if(!vis[i])
        {
            E temp=e[i];
            int mx=cal_max(temp.s,temp.t);
            ans=min(ans,mst-mx+temp.len);
        }
    }
    return ans==INF ? -1 : ans;
}

void work()
{
    int mst=kruskal();
    if(mst==sst(mst)) cout<<"Not Unique!"<<endl;
    else cout<<mst<<endl;
}

int main()
{
    cin>>t;
    while(t--)
    {
        read();
        work();
    }
}