AcWing 1148. Secret milk transportation problem solution (minimum spanning tree)

AcWing 1148. Secret milk transport
Their thinking ： First find the minimum spanning tree , Calculate the sum of the weights and mark all the edges in the minimum spanning tree . Then traverse all edges , Find the largest edge and the second largest edge on the path containing two points and record ,（ When two points find a new path to connect , Only which largest side is disconnected （t = sum - dist1[a][b] + w,dist1 Is the largest edge , It is concluded that the t Will be a smaller value , Then we can get the second smallest spanning tree ）, To ensure that the next small spanning tree is found , So record the largest edge , The second largest edge is recorded to prevent the largest edge from being used ）, Then traverse all the edges in the non minimum spanning tree , Replace the edges in the tree in turn , Finally, we find the second smallest spanning tree

Big guy problem solving original address

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 510, M = 2e4 + 10;

int n, m;
int p[N];  // Union checking set  
int dist1[N][N], dist2[N][N];  // Record the maximum value and the second maximum value on the corresponding edge path respectively 
ll res = 1e18;  // The final answer  
ll sum;  //  Record the weight of the minimum spanning tree 
int h[N], e[M], ne[M], w[M], idx;  // Record tree  

struct Edge{
    
	int a, b, w;
	bool f;  // Mark whether this edge is in the minimum spanning tree  
	bool operator< (const Edge &t) const {
    
		return w < t.w;
	}
}edg[M];

void add(int a, int b, int c){
    
	e[idx] = b;
	ne[idx] = h[a];
	w[idx] = c;
	h[a] = idx ++ ;
} 

int find(int x){
    
	if(x != p[x]) p[x] = find(p[x]);
	return p[x];
}

void dfs(int u, int fa, int mad1, int mad2, int d1[], int d2[]){
      // Find the maximum value and the second largest value on the path corresponding to each point  
	d1[u] = mad1, d2[u] = mad2;  //d1、d2 Array has no assignment before  
	for(int i = h[u]; ~i; i = ne[i]){
    
		int j = e[i];
		if(j != fa){
    
			int td1 = mad1, td2 = mad2;
			if(w[i] > td1){
    
				td2 = td1;
				td1 = w[i];
			}
			else if(w[i] < td1 && w[i] > td2){
    
				td2 = w[i];
			}
			dfs(j, u, td1, td2, d1, d2);
		}
	} 
}

signed main()
{
    
	cin>>n>>m;
	memset(h, -1, sizeof h);
	for(int i = 0; i < m; i ++ ){
    
		int a, b, c;
		cin>>a>>b>>c;
		edg[i] = {
    a, b, c};
	}
	
	// Find the smallest spanning tree  
	sort(edg, edg + m);
	for(int i = 1; i <= n; i ++ ) p[i] = i;
	
	for(int i = 0; i < m; i ++ ){
    
		int a = edg[i].a, b = edg[i].b, w = edg[i].w;  // Here we need to use points to build maps , therefore a、b Are used to express themselves  
		int pa = find(a), pb = find(b);
		if(pa != pb){
    
			sum += w;
			p[pa] = pb;
			add(a, b, w);
			add(b, a, w);
			edg[i].f = true; 
		}
	}
	
	// Find the maximum value and the second largest value of the path corresponding to each point 
	for(int i = 1; i <= n; i ++ ) dfs(i, -1, -1e9, -1e9, dist1[i], dist2[i]);
	
	for(int i = 0; i < m; i ++ ){
    
		if(!edg[i].f){
    
			int a = edg[i].a, b = edg[i].b, w = edg[i].w;
			ll t;
			if(w > dist1[a][b]){
    
				t = sum - dist1[a][b] + w;
			}
			else if(w > dist2[a][b]){
    
				t = sum - dist2[a][b] + w;
			}
			res = min(res, t);
		}
	} 
	cout<<res<<endl;
	return 0;
}