Brief description of topic meaning

Title Link

Given an undirected graph and two weights G and S, each edge in the graph has two weights au and ag. Find A spanning tree. Let the largest weight au in the tree edge be A and the largest weight ag be B. It is necessary to minimize the following formula: G*A+S*B.

Algorithm overview

[violence]

This problem requires a special minimum spanning tree. Obviously, Kruskal cannot directly find the minimum spanning tree with two-dimensional weight limit, so we consider fixing one dimension first.

Then enumerate each edge in turn, make A equal to the current au, then au is fixed, then Kruskal with the weight ag as the keyword, and finally the answer can be obtained. In the Kruskal process, note that if the currently enumerated edge is the one with the largest weight au in the final tree edge, then the weight au of the remaining edges must be less than or equal to it, and the one with the weight au greater than it can be directly screened out.

Time complexity O(m2logm).

[positive solution]

The bottleneck of violence algorithm mainly lies in Kruskal. We found that when the au of the current enumeration is A of the answer, the weight au of the remaining tree edges must be less than or equal to it. Therefore, we can think of sorting in ascending order with the weight au as the keyword, and then starting to enumerate each edge and fix the au. At this time, we do not need to enumerate all edges when Kruskal. Because the au of the tree edge of the answer must be less than the au of the current edge, we can directly find the answer in the edge before the current edge.

Then consider maintaining a stack. When enumerating with au as the keyword, press the edge into the stack. Each time when pressing the stack, maintain the monotonicity of ag as the keyword in the stack, and Kruskal's sorting operation can be omitted. Then, the edges in the stack are enumerated, Kruskal is performed, all the edges selected by Kruskal in each round are covered in the stack, and the stack is refreshed to ensure that there are only n-1 elements in the stack at most.

In this way, the time complexity can be maintained at O(nm).

Reference code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=210,M=5e4+10;
const ll INF=9223372036854775807;
struct Edge{
	int u,v,au,ag;
	bool operator <(const Edge &E)const
	{
		if(au!=E.au)return au<E.au;
		return ag<E.ag;
	}
}edge[M],stk[M];
int top;
int fa[N];
int n,m,G,S;
ll ans=INF;

int get(int x)
{
	if(fa[x]==x)return fa[x];
	return fa[x]=get(fa[x]);
}

int main()
{
	scanf("%d%d%d%d",&n,&m,&G,&S);
	
	for(int i=1;i<=m;i++)
		scanf("%d%d%d%d",&edge[i].u,&edge[i].v,&edge[i].au,&edge[i].ag);
	
	sort(edge+1,edge+m+1); //Sort in ascending order with au as the keyword 

	for(int i=1;i<=m;i++)
	{
		stk[++top]=edge[i]; //Stack pressing 
		
		for(int j=top;j>=2;j--)
			if(stk[j].ag<stk[j-1].ag)swap(stk[j],stk[j-1]); //Maintain the monotonicity of elements in the stack with ag as the keyword. This step replaces the sorting operation in the original Kruskal and reduces the time complexity. 
		
		int cnt=0;
		for(int i=1;i<=n;i++)fa[i]=i;
		for(int j=1;j<=top;j++) //The elements in the stack rise monotonically with ag as the keyword, so they can be enumerated directly in order 
		{
			int u=get(stk[j].u),v=get(stk[j].v);
			if(u==v)continue;
			fa[u]=v;
			stk[++cnt]=stk[j]; //Overwrite the elements in the stack and eliminate useless edges 
			if(cnt==n-1)break; //Up to n-1 tree edges 
		}
		if(cnt==n-1) //Update answer 
			ans=min(ans,(ll)G*edge[i].au+(ll)S*stk[cnt].ag);
		//You cannot directly break here because there may be smaller ag values that are not enumerated. The minimum value of all schemes shall be considered. 
		
		top=cnt;
	}
	
	if(ans==INF)printf("-1\n");
	else printf("%lld\n",ans);
	
	return 0;
}