題目描述：

有一天，pqq準(zhǔn)備去給×i×準(zhǔn)備禮物，他有一些禮品準(zhǔn)備包裝一下，他用線(xiàn)將這些禮物連在一起，不同的禮物因?yàn)轱L(fēng)格不同所以連接它們需要不同價(jià)值的線(xiàn)。風(fēng)格差異越大，價(jià)格越大(所以?xún)蓚€(gè)禮物之間只有一種連接價(jià)格），當(dāng)然有些禮物實(shí)在太不友好，所以有些禮物無(wú)法相連。pqq打算把所有禮物打包在一起，他不準(zhǔn)備花太多錢(qián)，但更不想花最少的錢(qián)（免得被拒絕）。所以他想知道第二便宜的包裝方案（可重復(fù)，pqq會(huì)認(rèn)為這是天命并直接選用最小代價(jià)來(lái)包裝禮物），同時(shí)，他還想知道最小的包裝代價(jià)以向×i×進(jìn)行炫耀。但是由于pqq不夠心靈手巧，所以他準(zhǔn)備找你來(lái)幫他計(jì)算答案。

?

輸入格式：

?兩個(gè)數(shù)n，m表示有n個(gè)禮物，有m對(duì)禮物可以相連1≤n,m≤2?105

?接下來(lái)的m行每行三個(gè)數(shù)a,b,c，表示a禮物和b禮物可以用c的價(jià)值相連 ,?1≤a,b≤n,1≤c≤106

?

輸出格式：

輸出一行，包含兩個(gè)數(shù)，分別是最小代價(jià)和次小代價(jià)

?

樣例輸入：

5 10 1 2 1 2 3 2 3 4 3 4 5 4 1 3 5 1 4 6 1 5 7 2 4 8 2 5 9 3 5 10

?

樣例輸出：

10 11

瞎扯：我其實(shí)很好奇XiX是誰(shuí)啊┐(′?｀)┌

題解：其實(shí)非嚴(yán)格次小生成樹(shù)的思路還是很好理解的
首先是什么是非嚴(yán)格次小生成樹(shù)
就是樹(shù)邊和可以等于和大于最小生成樹(shù)的另一顆生成樹(shù)
假設(shè)現(xiàn)在要把一條非樹(shù)邊(u,v,c)加入最小生成樹(shù)，想必要去掉一條原生成樹(shù)中u->v的邊，顯然去掉最大邊效果是最好的
所以在最小生成樹(shù)上跑一個(gè)倍增DP，d[i][j]表示j的2^i次祖先到j(luò)的路徑中最大的值
顯然可以跟跳lca一樣的在logn的跳出u->v路徑上的最大值，當(dāng)然樹(shù)鏈剖分也是可以搞這個(gè)東西的，但是再寫(xiě)一顆線(xiàn)段樹(shù)還享受lognlogn的復(fù)雜度
emmmm，何必呢……
如果能跳出這個(gè)值，我們只要枚舉每一條非樹(shù)邊，就可以在nlogn的復(fù)雜度里跳出非嚴(yán)格次小生成樹(shù)，然后就A掉了

代碼如下：
#include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define pii pair<int,int> #define mp make_pair #define int long long using namespace std;int fa[200010],vis[200010],deep[200010],n,m,f[19][250010],d[19][250010],ans1,ans2; vector<pii> g[200010]; struct line {int from,to,cost; }l[200010];int cmp(line a,line b) {return a.cost<b.cost; }void init() {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]); }void unity(int t,int x,int y,int c) {int fx=find(x);int fy=find(y);if(fx==fy) return ;fa[fx]=fy;ans1+=c;vis[t]=1; g[x].push_back(mp(y,c));g[y].push_back(mp(x,c)); }void dfs(int now,int ff,int dist,int dep) {d[0][now]=dist;f[0][now]=ff;deep[now]=dep;for(int i=1;i<=18;i++){f[i][now]=f[i-1][f[i-1][now]];}for(int i=1;i<=18;i++){d[i][now]=max(d[i-1][now],d[i-1][f[i-1][now]]);}for(int i=0;i<g[now].size();i++){if(g[now][i].first==ff) continue;dfs(g[now][i].first,now,g[now][i].second,dep+1);} }int get(int u,int v) {int x=u,y=v;if(deep[x]<deep[y]) swap(x,y);int di=0;for(int i=18;i>=0;i--){if(deep[f[i][x]]>=deep[y]){di=max(di,d[i][x]);x=f[i][x];}}if(x==y) return di;for(int i=18;i>=0;i--){if(f[i][x]!=f[i][y]){di=max(max(d[i][x],d[i][y]),di);x=f[i][x];y=f[i][y];}}return max(di,max(d[0][x],d[0][y])); }signed main() {scanf("%lld%lld",&n,&m);init();for(int i=1;i<=m;i++){scanf("%lld%lld%lld",&l[i].from,&l[i].to,&l[i].cost);}sort(l+1,l+m+1,cmp);for(int i=1;i<=m;i++){unity(i,l[i].from,l[i].to,l[i].cost);}dfs(1,0,0,1);ans2=1e16;for(int i=1;i<=m;i++){if(!vis[i]){ans2=min(ans2,ans1+l[i].cost-get(l[i].from,l[i].to));}}printf("%lld %lld\n",ans1,ans2); }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/stxy-ferryman/p/9325557.html

總結(jié)

以上是生活随笔為你收集整理的XJOI 3629 非严格次小生成树(pqq的礼物)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。