題目連結:http://61.187.179.132/JudgeOnline/problem.php?id=1977
題意:求一棵樹的嚴格次小生成樹,即權值嚴格大于最小生成樹且權值最小的生成樹。
思路:若現在已經得到了最小生成樹,那麼若 添加一條邊E,就會得到一個環,我們隻需要去掉環上權值小于E且最大的一條邊就會得到另一棵較優的生成樹。是以,隻需要枚舉不在生成樹上的邊,計算将其添 加到最小生成樹中得到的新生成樹的權值。取最小值即可。那麼,現在的問題就是在一個圈中找到一個最大的小于新添加的邊的權值的邊。由于最小生成樹是一棵 樹,可以利用最近公共祖先,并記錄路徑上權值的最大和次大值。則新加入的邊若大于圈上其他邊的最大值X,删掉X即可;否則掉圈上的次小值。
struct node
{
int u,v,w,flag;
};
node a[N<<2];
vector<pair<int,int> > g[N];
int f[N][20],dp1[N][20],dp2[N][20];
int n,m;
int cmp(node a,node b)
{
return a.w<b.w;
}
int p[N];
int get(int x)
{
if(p[x]!=x) p[x]=get(p[x]);
return p[x];
}
void add(int u,int v,int w)
{
g[u].pb(MP(v,w));
g[v].pb(MP(u,w));
}
int dep[N];
void DFS(int u,int pre)
{
int i,v;
FOR0(i,SZ(g[u]))
{
v=g[u][i].first;
if(v==pre) continue;
f[v][0]=u;
dp1[v][0]=g[u][i].second;
dp2[v][0]=-1;
dep[v]=dep[u]+1;
DFS(v,u);
}
}
void up(int &x,int y)
{
if(x==-1) x=y;
else if(x<y) x=y;
}
void init()
{
int i,j;
for(i=1;(1<<i)<=n;i++)
{
for(j=1;j+(1<<i)-1<=n;j++)
{
f[j][i]=f[f[j][i-1]][i-1];
dp1[j][i]=max(dp1[j][i-1],dp1[f[j][i-1]][i-1]);
dp2[j][i]=-1;
if(dp1[j][i-1]<dp1[j][i]) up(dp2[j][i],dp1[j][i-1]);
if(dp1[f[j][i-1]][i-1]<dp1[j][i]) up(dp2[j][i],dp1[f[j][i-1]][i-1]);
if(dp2[j][i-1]!=-1) up(dp2[j][i],dp2[j][i-1]);
if(dp2[f[j][i-1]][i-1]!=-1) up(dp2[j][i],dp2[f[j][i-1]][i-1]);
}
}
}
void up(int x,int &a,int &b)
{
if(x>a) b=a,a=x;
else if(x<a&&x>b) b=x;
}
int deal(int x,int a,int b)
{
if(x==a)
{
if(b==-1) return -1;
return x-b;
}
if(a==-1) return -1;
return x-a;
}
i64 cal(int t)
{
int u=a[t].u,v=a[t].v,w=a[t].w;
int Max1=-1,Max2=-1;
if(dep[u]>dep[v]) swap(u,v);
int x=dep[v]-dep[u];
int i;
for(i=0;i<20;i++) if(x&(1<<i))
{
up(dp1[v][i],Max1,Max2);
up(dp2[v][i],Max1,Max2);
v=f[v][i];
}
if(u==v) return deal(w,Max1,Max2);
for(i=19;i>=0;i--)
{
if(f[u][i]&&f[v][i]&&f[u][i]!=f[v][i])
{
up(dp1[u][i],Max1,Max2);
up(dp2[u][i],Max1,Max2);
up(dp1[v][i],Max1,Max2);
up(dp2[v][i],Max1,Max2);
u=f[u][i];
v=f[v][i];
}
}
up(dp1[u][0],Max1,Max2);
up(dp2[u][0],Max1,Max2);
up(dp1[v][0],Max1,Max2);
up(dp2[v][0],Max1,Max2);
return deal(w,Max1,Max2);
}
int main()
{
RD(n,m);
int i;
FOR1(i,m)
{
RD(a[i].u,a[i].v,a[i].w);
a[i].flag=1;
}
sort(a+1,a+m+1,cmp);
FOR1(i,n) p[i]=i;
i64 ans=0;
int u,v;
FOR1(i,m)
{
u=get(a[i].u);
v=get(a[i].v);
if(u==v) continue;
a[i].flag=0;
ans+=a[i].w;
add(a[i].u,a[i].v,a[i].w);
p[u]=v;
}
DFS(1,-1);
init();
i64 k=inf,temp;
FOR1(i,m) if(a[i].flag)
{
temp=cal(i);
if(temp!=-1&&temp<k) k=temp;
}
PR(ans+k);
}