題目描述:
有一天,pqq準備去給×i×準備禮物,他有一些禮品準備包裝一下,他用線将這些禮物連在一起,不同的禮物因為風格不同是以連接配接它們需要不同價值的線。風格差異越大,價格越大(是以兩個禮物之間隻有一種連接配接價格),當然有些禮物實在太不友好,是以有些禮物無法相連。pqq打算把所有禮物打包在一起,他不準備花太多錢,但更不想花最少的錢(免得被拒絕)。是以他想知道第二便宜的包裝方案(可重複,pqq會認為這是天命并直接選用最小代價來包裝禮物),同時,他還想知道最小的包裝代價以向×i×進行炫耀。但是由于pqq不夠心靈手巧,是以他準備找你來幫他計算答案。
輸入格式:
兩個數n,m表示有n個禮物,有m對禮物可以相連1≤n,m≤2∗105
接下來的m行每行三個數a,b,c,表示a禮物和b禮物可以用c的價值相連 , 1≤a,b≤n,1≤c≤106
輸出格式:
輸出一行,包含兩個數,分别是最小代價和次小代價
樣例輸入:
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
瞎扯:我其實很好奇XiX是誰啊┐(´∀`)┌
題解:其實非嚴格次小生成樹的思路還是很好了解的
首先是什麼是非嚴格次小生成樹
就是樹邊和可以等于和大于最小生成樹的另一顆生成樹
假設現在要把一條非樹邊(u,v,c)加入最小生成樹,想必要去掉一條原生成樹中u->v的邊,顯然去掉最大邊效果是最好的
是以在最小生成樹上跑一個倍增DP,d[i][j]表示j的2^i次祖先到j的路徑中最大的值
顯然可以跟跳lca一樣的在logn的跳出u->v路徑上的最大值,當然樹鍊剖分也是可以搞這個東西的,但是再寫一顆線段樹還享受lognlogn的複雜度
emmmm,何必呢……
如果能跳出這個值,我們隻要枚舉每一條非樹邊,就可以在nlogn的複雜度裡跳出非嚴格次小生成樹,然後就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);
}