生活随笔
收集整理的這篇文章主要介紹了
Luogu P1967 NOIP2013 货车运输
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
這個題是很經典的生成樹問題。第一次接觸時對倍增算法的理解還不夠透徹，沒能打出來正解。
首先，原題中給出的是一幅圖，詢問從某點出發到另一點“需要經過的最短邊的最大值”。用floyd來解決是可以的，但是數據范圍不能承受O(n^3)的復雜度。于是我們考慮：假設原圖是連通的，那么我們從某點到另一點，一定至少存在一條路徑；而明顯有一條路徑是最優的，滿足它所經過的最小邊最大。既然這樣，我們能不能把這條路徑找出來呢？于是我們想對原圖做一些處理。新的圖應該滿足：
1. 圖仍是連通的。
2. 任意兩點間的一條路徑滿足上述最優條件。
于是我們想到了生成樹。從貪心的角度考慮，兩點之間一定有一條這樣的最優路徑是最大生成樹上的唯一路徑。說明：因為最大生成樹外的一條邊一定小于等于樹上的邊權，那么它不可能比這條樹上路徑更優。
求出MST后，我們要維護的是樹上路徑的最小值信息。路徑本身可以用LCA來搞，可是路徑上的信息怎么預處理呢？聯想ST算法，我們雖然不能維護任意兩點間的信息，但是可以用倍增的思想，維護w(i, k)表示節點i到它的2^k代祖先所需經過的最短路徑。w(i, 0)就是生成樹上該點入邊的權，然后按k從小到大轉移，轉移方程w(i, k) = min(w(i, k - 1), w(f[i][k-1], k-1))。其中f數組是按倍增法求LCA記錄的祖先信息。最后查詢時，所求的ans隨LCA倍增算法更新最小值即可。
注意原圖是不連通的，我們生成的實際上是一個森林，kruscal算法里維護的并查集可以幫助判斷兩個點是否在一個聯通塊內。
代碼：
#include?<iostream>??#include?<cstdio>??#include?<cstring>??#include?<cctype>??#include?<algorithm>??#define?maxn?10010??#define?maxm?50010??#define?inf?(int)2e9??using?namespace?std;??template?<typename?T>???void?read(T?&x)?{??????x?=?0;??????char?ch?=?getchar();??????while?(!isdigit(ch))?ch?=?getchar();??????while?(isdigit(ch))?{??????????x?=?x?*?10?+?(ch?^?48);??????????ch?=?getchar();??????}??????return;??}??int?n,?m,?q;??int?head[maxn],?top?=?1;??struct?E?{??????int?to,?nxt,?w;??}?edge[maxn?<<?1];??struct?pE?{??????int?u,?v,?w;??}?pedge[maxm];??bool?cmp(pE?a,?pE?b)?{??????return?a.w?>?b.w;??}??inline?void?insert(int?u,?int?v,?int?w)?{??????edge[++top]?=?(E)?{v,?head[u],?w};??????head[u]?=?top;??}??namespace?UFS?{??????int?fa[maxn],?rk[maxn];??????void?init1()?{??????????for?(int?i?=?1;?i?<=?n;?++i)??????????????fa[i]?=?i;??????}??????int?find(int?x)?{??????????if?(fa[x]?==?x)?return?x;??????????return?fa[x]?=?find(fa[x]);??????}??????bool?Union(int?u,?int?v)?{??????????u?=?find(u),?v?=?find(v);??????????if?(u?==?v)?return?false;??????????if?(rk[u]?<?rk[v])?swap(u,?v);??????????fa[v]?=?u;??????????rk[u]?=?max(rk[u],?rk[v]?+?1);??????????return?true;??????}??}?using?namespace?UFS;??void?kruscal()?{??????init1();??????sort(pedge?+?1,?pedge?+?1?+?m,?cmp);??????for?(int?i?=?1,?cnt?=?0;?i?<=?m?&&?cnt?<?n?-?1;?++i)?{??????????int?u?=?pedge[i].u,?v?=?pedge[i].v,?w?=?pedge[i].w;??????????if?(Union(u,?v))?{??????????????insert(u,?v,?w),?insert(v,?u,?w);??????????????++cnt;??????????}??????}??}??namespace?LCA?{??????const?int?LG(14);??????int?w[LG+2][maxn],?f[LG+2][maxn],?d[maxn];??????bool?vis[maxn];??????void?dfs(int?u,?int?pre,?int?depth)?{??????????d[u]?=?depth;??????????f[0][u]?=?pre;??????????vis[u]?=?true;??????????for?(int?i?=?head[u];?i;?i?=?edge[i].nxt)?{??????????????int?v?=?edge[i].to;??????????????if?(vis[v])?continue;??????????????w[0][v]?=?edge[i].w;??????????????dfs(v,?u,?depth?+?1);??????????}??????}??????void?init2()?{??????????for?(int?i?=?1;?i?<=?n;?++i)?{??????????????if?(vis[i])?continue;??????????????dfs(i,?0,?1);??????????}??????????for?(int?k?=?1;?k?<=?LG;?++k)??????????????for?(int?i?=?1;?i?<=?n;?++i)?{?????????????????????f[k][i]?=?f[k-1][f[k-1][i]];??????????????????w[k][i]?=?min(w[k-1][i],?w[k-1][f[k-1][i]]);??????????????}??????}??????int?query(int?u,?int?v)?{??????????if?(find(u)?!=?find(v))?return?-1;??????????int?ans?=?inf;??????????if?(d[u]?>?d[v])?swap(u,?v);??????????int?del?=?d[v]?-?d[u];??????????for?(int?i?=?0;?del;?++i,?del?>>=?1)??????????????if?(del?&?1)???????????????????ans?=?min(ans,?w[i][v]),?v?=?f[i][v];??????????if?(u?==?v)?return?ans;??????????for?(int?i?=?LG;?i?>=?0;?--i)??????????????if?(f[i][u]?!=?f[i][v])?{???????????????????ans?=?min(ans,?min(w[i][u],?w[i][v]));??????????????????u?=?f[i][u],?v?=?f[i][v];??????????????}??????????return?min(ans,?min(w[0][u],?w[0][v]));??????}??}?using?namespace?LCA;???int?main()?{??????read(n),?read(m);??????int?u,?v,?w;??????for?(int?i?=?1;?i?<=?m;?++i)?{??????????read(u),?read(v),?read(w);??????????if?(u?!=?v)??????????????pedge[i]?=?(pE)?{u,?v,?w};??????}??????kruscal();??????init2();??????read(q);??????while?(q--)?{??????????read(u),?read(v);??????????printf("%d\n",?query(u,?v));??????}??????return?0;??} ?PS：看了這個題以后覺得樹剖貌似是個好東西，有空學習一個。
（7.16）樹上路徑最小邊權用樹剖維護的確是很顯然的，之后可以打一下。
（8.2）今日一份樹剖奉上，開啟我的暑假中二學習之旅。
轉載于:https://www.cnblogs.com/TY02/p/11132814.html
總結
以上是生活随笔為你收集整理的Luogu P1967 NOIP2013 货车运输的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
