**解题报告：**这还是个定理吧，就是说我们可以删掉最小生成树的一条树边，然后加上该点的树边，就能形成一个生成树，（如上图p2，绿色的边是两个点之间的最长树边，我们可以把他删掉，加上蓝色的边，这样并不影响它的连通性，所以他还是生成树）那么就一定有他的值是sum-l+w，为了让这个值最小并且比sum大，sum指的是最小生成树所有和，那么一定要找到a,b之间的最大树边（a,b指的是w边的两个顶点），这个可以dfs做，然而这样并不一样对，看上图p3,墨染空大佬就指出了一个错误，当两点之间的距离如果等于这条边，在原做法里面就不会更新了，然而我们可以更新次大值，不得不说是真的强啊。当然在dfs的时候，我们要注意，不要直接用maxd和maxd2，要用两个变量次次存放这两条边，因为在不同邻边下，条件是不一样的，同时更新次大值的时候，注意是严格次大值（就是不能和最大值相等）。
#include<bits/stdc++.h>
using namespace std;
const int N = 510, M=10010;
typedef long long ll;
int dist[N][N];
int dist2[N][N];
int n,m;
int h[N],e[N*2],w[N*2],idx,ne[N*2];
int p[N];
struct node{
int a;
int b;
int w;
bool f;
bool operator <(const node&W) const
{
return w<W.w;
}
}q[M];
int find(int x)
{
if(x!=p[x])
p[x] = find(p[x]);
return p[x];
}
void add(int a,int b,int c)
{
w[idx] = c ,ne[idx]=h[a], e[idx] = b ,h[a]= idx++;
}
void dfs(int u,int fa,int maxd,int maxd2,int d[],int d2[])
{
d[u] = maxd;
d2[u] = maxd2;
for(int i=h[u];~i;i=ne[i])
{
int t1=maxd;
int t2 = maxd2;
int j=e[i];
if(j==fa) continue;
if(w[i]>t1) t2=t1,t1 = w[i];
else if(w[i]<t1&&w[i]>t2) t2 = w[i];
dfs(j,u,t1,t2,d,d2);
}
}
int main()
{
cin >> n >> m;
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
q[i]={
a,b,c};
}
sort(q,q+m);
for(int i=1;i<=n;i++)
p[i] = i;
ll sum=0;
memset(h,-1,sizeof h);
for(int i=0;i<m;i++)
{
int pa = find(q[i].a) , pb = find(q[i].b) , c = q[i].w;
int a=q[i].a,b=q[i].b;
if(pa!= pb)
{
sum += c;
p[pa] = pb;
add(a,b,c);
add(b,a,c);
q[i].f=true;
}
}
for(int i=1;i<=n;i++) dfs(i,-1,0,-1e9,dist[i],dist2[i]);
ll res = 1e18;
for(int i=0;i<m;i++)
{
if(!q[i].f)
{
int a = q[i].a , b=q[i].b ,c =q[i].w;
if(c>dist[a][b])
{
res = min(res,sum-dist[a][b]+c);
}
else if(c>dist2[a][b])
res = min(res,sum-dist2[a][b]+c);
}
}
cout << res <<endl;
return 0;
}
京公网安备 11010502036488号