一种新的求次小生成树的方法
(暴力枚举) $O(nm)$
先建成一棵最小生成树,枚举每一条边被替换后的结果,如果当前边被替换后值仍然与最小生成树的值相同,证明该图存在多棵最小生成树,此时寻找到一条边比最小生成树的最大边大,直接替换即可,如果找不到这条边或者无法构成树,证明该边不可替换。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 510, M = 1e4 + 10;
struct Edge{
int u, v, w;
bool operator<(const Edge& a) const{
return w < a.w;
}
}e[M];
int n, m;
int fa[N];
vector<int> s;
int flag;
int find(int x){
if(x != fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
int krusual(int x){
for(int i = 1; i <= n; i++) fa[i] = i;
int ans = 0;
int cnt = 0;
for(int i = 0; i < m; i++){
if(i == s[x]) continue;
auto[u, v, w] = e[i];
int ru = find(u), rv = find(v);
if(ru != rv){
cnt++;
ans += w;
fa[rv] = ru;
}
}
int temp = 0;
for(int i = 0; i < m; i++){
if(e[i].w > e[s.back()].w){
temp = e[i].w - e[s.back()].w;
break;
}
}
if(cnt != n - 1) return 1e18;
if(ans == flag && temp){
return ans + temp;
}
else if(ans == flag) return 1e18;
return ans;
}
signed main(){
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) fa[i] = i;
for(int i = 0; i < m; i++){
cin >> e[i].u >> e[i].v >> e[i].w;
}
sort(e, e + m);
for(int i = 0; i < m; i++){
auto[u, v, w] = e[i];
int ru = find(u), rv = find(v);
if(ru != rv){
s.push_back(i);
flag += w;
fa[rv] = ru;
}
}
int ans = 1e18;
for(int i = 0; i < s.size(); i++){
ans = min(ans, krusual(i));
}
cout << ans << "\n";
return 0;
}