次小生成樹 Tree-LCA的位運算

　　關於次小生成樹 TreeLCA的位運算我們有實例!

　　小 C 最近學了很多最小生成樹的算法Prim 算法Kurskal 算法消圈算法 等等 正當小 C 洋洋得意之時小 P 又來潑小 C 冷水了小 P 說讓小 C 求出一 個無向圖的次小生成樹而且這個次小生成樹還得是嚴格次小的也就是說 如果最小生成樹選擇的邊集是 EM嚴格次小生成樹選擇的邊集是 ES那麼 需要滿足(value(e) 表示邊 e的權值) 這下小 C 蒙了他找到了你希望你幫他解決這個問題

　　Input

　　第一行包含兩個整數N 和M表示無向圖的點數與邊數 接下來 M行每行 個數x y z 表示點 x 和點y之間有一條邊邊的權值 為z

　　Output

　　包含一行僅一個數表示嚴格次小生成樹的邊權和(數 據保證必定存在嚴格次小生成樹)

　　Sample Input

　　

　　

　　

　　

　　

　　

　　

　　Sample Output

　　

　　HINT

　　數據中無向圖無自環;

　　% 的數據N≤ M≤ ;

　　% 的數據N≤ M≤ ;

　　% 的數據N≤ M≤ 邊權值非負且不超過 ^

　　

　　Source

　　這題的關鍵就在於求Lca記錄路徑上的最小與嚴格次小值

　　用f[i][j]表示i的第^j個兒子( 表示 不存在)

　　那麼f[i][j]=f[ f[i][ j] ][j]

　　dp[i][j]和dp[i][j]表示點i到f[i][j]的最小和嚴格次小值(不存在=)那麼只需特判即可

　　[cpp]

　　int lca(int xint yint &nowdpint &nowdp)

　　{

　　if (deep[x]<deep[y]) swap(xy);

　　int t=deep[x]deep[y]; //差的數量

　　for (int i=;t;i++)

　　if (t&bin[i]) //轉化為位運算 bin[i]表示<<i 把t看成進制

　　{

　　x=f[x][i];

　　t=bin[i];

　　}

　　int i=Li; //Li 表示 最高存到^(Li)個父親

　　while (x^y) //x和y不相等時

　　{

　　while (f[x][i]==f[y][i]&&i) i; //當i==時只能向上跳

　　x=f[x][i];y=f[y][i];

　　}

　　}

　　程序

　　[cpp]

　　#include<cstdio>

　　#include<cstdlib>

　　#include<cstring>

　　#include<iostream>

　　#include<algorithm>

　　#include<functional>

　　using namespace std;

　　#define MAXN (+)

　　#define MAXM (+)

　　#define Li ()

　　#define INF ()

　　int edge[MAXM]pre[MAXM]weight[MAXM]next[MAXM]size=;

　　int addedge(int uint vint w)

　　{

　　edge[++size]=v;

　　weight[size]=w;

　　next[size]=pre[u];

　　pre[u]=size;

　　}

　　int addedge(int uint vint w)

　　{

　　addedge(uvw);

　　addedge(vuw);

　　}

　　int f[MAXN][Li]={}dp[MAXN][Li]={}dp[MAXN][Li]={}deep[MAXN]nm;

　　struct E

　　{

　　int uvw;

　　friend bool operator<(E aE b){return aw<bw; }

　　}e[MAXM];

　　bool b[MAXM]vis[MAXN];

　　int queue[MAXN]headtail;

　　void bfs()

　　{

　　memset(vissizeof(vis));

　　head=tail=;queue[]=;vis[]=;deep[]=;

　　while (head<=tail)

　　{

　　int &u=queue[head];

　　if (u!=)

　　{

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

　　{

　　if (f[u][i])

　　{

　　f[u][i]=f[f[u][i]][i];

　　}

　　if (f[u][i]==) break;

　　if (f[u][i])

　　{

　　dp[u][i]=max(dp[u][i]dp[f[u][i]][i]);

　　}

　　if (i==)

　　{

　　if (dp[u][]!=dp[f[u][]][]) dp[u][]=min(dp[u][]dp[f[u][]][]);

　　else dp[u][]=;

　　}

　　else

　　{

　　dp[u][i]=max(dp[u][i]dp[f[u][i]][i]);

　　if (dp[u][i]!=dp[f[u][i]][i]) dp[u][i]=max(dp[u][i]min(dp[u][i]dp[f[u][i]][i]));

　　}

　　}

　　}

　　for (int p=pre[u];p;p=next[p])

　　{

　　int &v=edge[p];

　　if (!vis[v])

　　{

　　queue[++tail]=v;

　　vis[v]=;deep[v]=deep[u]+;

　　f[v][]=u;dp[v][]=weight[p];dp[v][]=;

　　}

　　}

　　head++;

　　}

　　}

　　int bin[Li];

　　void check(int &nowdpint &nowdpint c)

　　{

　　if (c<=nowdp) return;

　　else if (nowdp<c&&c<nowdp) nowdp=c;

　　else if (c==nowdp) return;

　　else if (nowdp<c) {nowdp=nowdp;nowdp=c;}

　　}

　　int lca(int xint yint &nowdpint &nowdp)

　　{

　　nowdp=nowdp=;

　　if (deep[x]<deep[y]) swap(xy);

　　int t=deep[x]deep[y];

　　for (int i=;t;i++)

　　if (t&bin[i])

　　{

　　check(nowdpnowdpdp[x][i]);

　　check(nowdpnowdpdp[x][i]);

　　x=f[x][i];

　　t=bin[i];

　　}

　　int i=Li;

　　while (x^y)

　　{

　　while (f[x][i]==f[y][i]&&i) i;

　　check(nowdpnowdpdp[x][i]);

　　check(nowdpnowdpdp[x][i]);

　　check(nowdpnowdpdp[y][i]);

　　check(nowdpnowdpdp[y][i]);

　　x=f[x][i];y=f[y][i];

　　}

　　}

　　int father[MAXN];

　　long long sum_edge=;

　　int getfather(int x)

　　{

　　if (father[x]==x) return x;

　　father[x]=getfather(father[x]);

　　return father[x];

　　}

　　void union(int xint y)

　　{

　　father[father[x]]=father[father[y]];

　　}

　　int main()

　　{

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

　　for (int i=;i<=n;i++) father[i]=i;

　　memset(bsizeof(b));

　　memset(nextsizeof(next));

　　for (int i=;i<Li;i++) bin[i]=<<i;

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

　　{

　　scanf(%d%d%d&e[i]u&e[i]v&e[i]w);

　　}

　　sort(e+e++m);

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

　　{

　　if (getfather(e[i]u)!=getfather(e[i]v)) {union(e[i]ue[i]v);addedge(e[i]ue[i]ve[i]w);sum_edge+=e[i]w; }

　　else b[i]=;

　　}

　　bfs();

　　long long mindec=;

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

　　if (b[i])

　　{

　　int nowdpnowdp;

　　lca(e[i]ue[i]vnowdpnowdp);

　　if (nowdp==e[i]w) nowdp=nowdp;

　　if (nowdp==) continue;

　　if (mindec==||mindec>e[i]wnowdp) mindec=e[i]wnowdp;

　　}

　　printf(%lld\nsum_edge+mindec);

　　return ;

　　}

From:http://tw.wingwit.com/Article/program/Java/hx/201311/26453.html