求出次小生成树和最小生成树的边权和,比较是否相等
求次小生成树方法
方法1:
先求最小生成树,再枚举删去最小生成树中的边求解
方法2:
先求最小生成树,然后依次枚举非树边,然后将该边加入树中,同时从树中去掉一条边,
使得最终的图仍是一棵树,则一定可以求出次小生成树
参考代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510,M=1e4+5;
typedef long long LL;
int n,m;
int d1[N][N],d2[N][N];
int e[N*2],ne[N*2],h[N],idx,w[N*2];
struct Node{
int a,b,w;
bool f;
bool operator <(Node x) const
{
return w<x.w;
}
}a[M];
LL sum,ans=1e18;
int p[N];
void init()
{
ans=1e18;
sum=0;
memset(h,-1,sizeof h);
memset(d1,0,sizeof d1);
memset(d2,0,sizeof d2);
idx=0;
}
void add(int a,int b,int c)
{
w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
void dfs(int u,int v,int t1,int t2,int d1[],int d2[])
{
d1[u]=t1,d2[u]=t2;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==v) continue;
int x=t1,y=t2;
if(w[i]>t1) y=x,x=w[i];
else if(w[i]>t2&&w[i]<t1) y=w[i];
dfs(j,u,x,y,d1,d2);
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
init();
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++) p[i]=i;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
a[i].f=0;
a[i]={x,y,z};
}
sort(a+1,a+1+m);
for(int i=1;i<=n;i++) p[i]=i;
// 求最小生成树
for(int i=1;i<=m;i++)
{
int x=find(a[i].a),y=find(a[i].b);
if(x!=y)
{
sum+=a[i].w;
a[i].f=1;
add(a[i].a,a[i].b,a[i].w);
add(a[i].b,a[i].a,a[i].w);
p[x]=y;
}
}
for(int i=1;i<=n;i++) dfs(i,-1,-1e9,-1e9,d1[i],d2[i]);
//求次小生成树
for(int i=1;i<=m;i++)
{
if(!a[i].f)
{
LL k;
int x=a[i].a,y=a[i].b;
if(a[i].w>=d1[x][y]) k=sum+a[i].w-d1[x][y];
else if(a[i].w>=d2[x][y]) k=sum+a[i].w-d2[x][y];
ans=min(ans,k);
}
}
if(sum==ans) cout<<"No"<<'\n';
else cout<<sum<<'\n';
}
return 0;
}