小C最近學了很多最小生成樹的算法,Prim算法、Kurskal算法、消圈算法等等。正當小C洋洋得意之時,小P又來潑小C冷水了。小P說,讓小C求出一個無向圖的次小生成樹,而且這個次小生成樹還得是嚴格次小的,也就是說:如果最小生成樹選擇的邊集是EM,嚴格次小生成樹選擇的邊集是ES,那麼需要滿足:(value(e)表示邊e的權值) \sum_{e \in E_M}value(e)<\sum_{e \in E_S}value(e)∑e∈EMvalue(e)<∑e∈ESvalue(e)
這下小 C 蒙了,他找到了你,希望你幫他解決這個問題。
輸入輸出格式
輸入格式:
第一行包含兩個整數N 和M,表示無向圖的點數與邊數。 接下來 M行,每行 3個數x y z 表示,點 x 和點y之間有一條邊,邊的權值為z。
輸出格式:
包含一行,僅一個數,表示嚴格次小生成樹的邊權和。(資料保證必定存在嚴格次小生成樹)
輸入輸出樣例
輸入樣例#1:
5 6
1 2 1
1 3 2
2 4 3
3 5 4
3 4 3
4 5 6
輸出樣例#1:
11
題解:嚴格次小生成樹和非嚴格次小生成樹的思想其實差不多,無非是多元護一個u->v之間的次大值
然後這顯然也是能用倍增維護的
如果把最大邊拆去換成新邊後整棵樹仍是最小生成樹,那麼就換次大邊用,再不對就不用
這樣能保證求出的一定不是最小生成樹,是以是嚴格次小的
代碼如下:
#pragma GCC optimize(3)
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mp make_pair
#define int long long
#define pii pair<long long,long long>
using namespace std;
struct node
{
int from,to,cost;
} e[500010];
int n,m,f[200010],ans,ans1,vis[200010],fa[19][200010],d1[19][200010],d2[19][200010],deep[200010];
vector<pii> g[200010];
int cmp(node a,node b)
{
return a.cost<b.cost;
}
void dfs(int now,int ff,int dep,int dis)
{
deep[now]=dep;
d1[0][now]=dis;
fa[0][now]=ff;
for(int i=1; i<=18; i++)
{
fa[i][now]=fa[i-1][fa[i-1][now]];
}
for(int i=1; i<=18; i++)
{
register int a[4];
a[0]=d1[i-1][now];
a[1]=d1[i-1][fa[i-1][now]];
a[2]=d2[i-1][now];
a[3]=d2[i-1][fa[i-1][now]];
sort(a,a+4);
d1[i][now]=a[3];
d2[i][now]=a[2];
}
for(int i=0; i<g[now].size(); i++)
{
if(g[now][i].first==ff) continue;
dfs(g[now][i].first,now,dep+1,g[now][i].second);
}
}
pii get1(int u,int v)
{
int di=0ll,di2=0ll;
if(deep[u]<deep[v]) swap(u,v);
for(int i=18; i>=0; i--)
{
if(deep[fa[i][u]]>=deep[v])
{
register int a[4];
a[0]=di;
a[1]=di2;
a[2]=d1[i][u];
a[3]=d2[i][u];
sort(a,a+4);
di=a[3];
di2=a[2];
u=fa[i][u];
}
}
if(u==v) return mp(di,di2);
for(int i=18; i>=0; i--)
{
if(fa[i][u]!=fa[i][v])
{
register int a[6];
a[0]=di;
a[1]=di2;
a[2]=d1[i][u];
a[3]=d1[i][v];
a[4]=d2[i][u];
a[5]=d2[i][v];
sort(a,a+6);
di=a[5];
di2=a[4];
u=fa[i][u];
v=fa[i][v];
}
}
register int a[6];
a[0]=di;
a[1]=di2;
a[2]=d1[0][u];
a[3]=d1[0][v];
a[4]=d2[0][u];
a[5]=d2[0][v];
sort(a,a+6);
di=a[5];
di2=a[4];
return mp(di,di2);
}
void init()
{
for(int i=1; i<=n; i++)
{
f[i]=i;
}
}
int find(int x)
{
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
void unity(int i,int x,int y,int cost)
{
int fx=find(x);
int fy=find(y);
if(fx==fy) return ;
ans+=cost;
f[fy]=fx;
g[x].push_back(mp(y,cost));
g[y].push_back(mp(x,cost));
vis[i]=1;
}
signed main()
{
scanf("%lld%lld",&n,&m);
init();
for(int i=1; i<=m; i++)
{
scanf("%lld%lld%lld",&e[i].from,&e[i].to,&e[i].cost);
}
sort(e+1,e+m+1,cmp);
for(int i=1; i<=m; i++)
{
unity(i,e[i].from,e[i].to,e[i].cost);
}
dfs(1,0,0,0);
ans1=1e16;
for(int i=1; i<=m; i++)
{
if(!vis[i])
{
pii tmp=get1(e[i].from,e[i].to);
int ans2=ans-tmp.first+e[i].cost;
int ans3=ans-tmp.second+e[i].cost;
if(ans==ans2)
{
if(ans<ans3) ans1=min(ans1,ans3);
}
else
{
ans1=min(ans1,ans2);
}
}
}
printf("%lld\n",ans1);
}