次小生成树

次小生成树

简介：

求权值和第二小的生成树的权值之和

解法：

我们考虑当前已经构成的一颗最小生成树，说明此时所选的所有边是满足权值和最小的，当我们枚举一条新边时，如果将其加入已经构成的最小生成树则可能会构成一个环，我们只需要将环上的最大边去掉，此时就形成了次小生成树。【原因：所谓次小生成树就会和最小生成树有一条边不同，当我们枚举所有边每次考虑当前边的影响取最小后，得到的就是次小生成树】

具体做法：

1. 构造mst最小生成树
2. 将mst连起来
3. dfs遍历整个最小生成树，求出dp[v][k],点v,k成环后环中的最大权值
4. 遍历所有非mst边，考虑其影响【minn2 = min(minn2,mst-dp[v][k]+w)】即mst去除环中最大权值加入当前边后构成的生成树权值和，取所有影响的min即得到次小生成树

代码实现：

例：UVA - 10600

#include<bits/stdc++.h>
using namespace std;
# define int long long
# define endl "\n"
const int N = 1e3+10,M = 5e3+10, inf = 0x3f3f3f3f;
struct node {
	int a, b, w;
} edg[M];
bool cmp(node a, node b) {
	return a.w < b.w;
}
int f[N];
int find(int x){
	if(x == f[x]) return x;
	else return f[x] = find(f[x]);
}
int n, m;
vector<pair<int,int>> e[M];
bool inmst[M];
int mst() {
	for (int i = 1; i <= n; ++i) {
		f[i] = i;
	}
	memset(inmst,0,sizeof inmst);
	sort(edg+1,edg+1+m,cmp);
	int cnt = 0;
	int ans = 0;
	for(int i = 1;i <= m;++i){
		int x = edg[i].a,y = edg[i].b,w = edg[i].w;
		int fx = find(x),fy = find(y);
		if(fx != fy){
			f[fx] = fy;
			/*将mst连起来*/ 
			inmst[i] = 1;
			e[x].push_back({y,w});
			e[y].push_back({x,w});
			cnt++;
			ans += w;
			if(cnt == (n-1)) break;
		}
	}
	return ans;
}
int dp[N][N],vis[N];

void dfs(int u){
	vis[u] = 1;
	for(int i = 0;i < e[u].size();++i){
		int v = e[u][i].first,w = e[u][i].second;
		if(vis[v]) continue;
		for(int k = 1;k <= n;++k){
			if(vis[k]){ 
				dp[k][v] = dp[v][k] = max(dp[k][u],w);
			}
		}
		dfs(v);
	}
}
void solve() {

	cin >> n >> m;
	for(int i = 1;i <= n;++i){
		e[i].clear();
	}
	/*读边*/
	for (int i = 1; i <= m; ++i) {
		int a, b, w;
		cin >> a >> b >> w;
		edg[i] = {a, b, w};
	}
	/*1.求mst并将mst连起来*/ 
	int minn = mst();
	memset(dp,0,sizeof dp);
	memset(vis,0,sizeof vis);
	/*2.dfs求dp[v][k]，v,k成环后环中的最大权值*/
	dfs(1);
	int minn2 = inf;
	/*3.遍历所有非mst边，考虑其影响*/ 
	for(int i = 1;i <= m;++i){
		if(inmst[i]) continue;//若该边在mst中则跳过 
		int x = edg[i].a,y = edg[i].b,w = edg[i].w;
		minn2 = min(minn2,minn-dp[x][y]+w);
	}
	cout<<minn<<" "<<minn2<<endl;
	

}
int tt;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	tt = 1;
	cin >> tt;
	while (tt--) solve();


	return 0;
}